1783

날짜 : 2022. 11. 09

사용 언어 : python

 

문제

 

 

코드

삼천포로 빠져버린 코드..

import sys

n, m = map(int, sys.stdin.readline().split())
knight = [n - 1, 0]
chess = [[False] * m for i in range(n)]
chess[knight[0]][knight[1]] = True
dx = [-2, -1, 1, 2]
dy = [1, 2, 2, 1]


def go(a, b, arr):
    print(a, b)
    if len(arr) > 0:
        for i in arr:
            x = a + dx[i]
            y = b + dy[i]
            print(x, y)
            if x in range(n) and y in range(m) and chess[x][y] == False:
                chess[x][y] = True
                temp = arr
                temp.remove(i)
                go(x, y, temp)
    else:
        for i in range(4):
            x = a + dx[i]
            y = b + dy[i]
            if x in range(n) and y in range(m) and chess[x][y] == False:
                chess[x][y] = True
                go(x, y, [])

    return


go(knight[0], knight[1], [0, 1, 2, 3])
cnt = 0
for i in range(n):
    for j in range(m):
        if chess[i][j] == True: cnt += 1

print(cnt)
for i in chess:
    print(i)

 

정답코드

import sys
n, m = map(int, sys.stdin.readline().split()) # 세로, 가로 입력

if n == 1: print(1) # 세로가 1
elif n == 2: print(min(4, (m + 1) // 2)) # 세로가 2(4회까지는 자유롭게, 이후에는 모든 경우의수 필요)
else: # 세로가 3 이상
    if m <= 6: print(min(4, m)) # 가로가 6 이하 : 4 또는 가로길이(1, 4번째 방식으로 와리가리)
    else: print(m-2) # 가로가 6 초과 : 가로길이 - 2 (2, 3 케이스로 인한 2 차감 후 와리가리(오른쪽 1칸씩) 이동)

 

 

알게된 점

- DFS로 풀이하는 문제라서 자연스럽게 풀었는데 왠걸 삼천포로 빠져버렸다.

- 그래서 한참을 생각해본 결과 답이 안보여서 구글링을 했고 세로의 케이스, 가로의 케이스를 나눔으로써 풀 수 있는 문제라는 것을 알게 되었다.

- 먼저 문제조건을 이해하는데 오래걸렸고, 풀이방법을 이해하는데도 오래걸렸다. 문제상에서 약간의 힌트로 n, m값을 20억이라는 큰 값으로 줬는데 이를 캐치하지 못했다;;

- 요즘 그리디 문제를 잘 안풀었는데 다시 공부해야겠다는 의지가 생긴다.

 

- 풀이는 다음과 같다.

- 세로가 1인 경우에는 모든 이동방법이 불가능하기 때문에 답은 1로 고정

- 세로가 2인 경우에는 이동은 가능하지만 (우1 위2), (우1 아래2) 두가지 방법으로 이동이 가능하다.

    다만, 4번의 이동까지만 2, 3번의 반복적인 사용이 가능하고 이후에는 불가능하다.

    (5회 이상 이동하는 경우 1~4번의 이동방식을 모두 사용해야 한다.)

  => 그래서 해당 케이스인 경우에는 자유롭게 이동하는 방식의 최대한도인 4와 그 아래인 경우의수를 비교하여 출력한다.

- 세로가 3 이상인 경우에는 가로가 6 이하, 6 초과인 경우를 분리하여 출력한다.

   가로길이가 6 이하인 경우는 우측으로 이동하되 2칸으로 이동하는 경우가 1회, 1, 4번째 방식(우1, 위/아래2)으로만 움직이는 경우가 2회이기 때문에 4가 최대이며 그 이하인 경우(우1 위/아래2 방식으로만 이동)인 경우의수와 비교하여 작은 수를 출력한다.

  가로길이가 6보다 큰 경우는 2, 3번째 방식(우2 위/아래1)으로 이동한 경우를 제외하고 우측으로 1칸만 이동하는 방식을 사용하면 되기 때문에 이동방향에 관계없이 m-2를 출력하면 된다.

 

 

 

 

참고 사이트

-