[백준 Python] 18248번 제야의 종

백준 18248 제야의 종 (실버 2)

문제

제야의 종 타종은 한 해의 끝과 새로운 한 해의 시작을 알리는 행사이다. 이 행사에서는 보신각의 종을 여러 번 타종한다.

제야의 종을 타종해서 나는 종소리는 종으로부터 특정 거리 R 이내에 있는 사람은 모두 들을 수 있고, R보다 멀리 떨어져 있는 사람은 모두 들을 수 없는 특징을 가지고 있다. 여러 명의 정치인, 연예인 등의 유명 인사가 돌아가며 타종하기 때문에 매번 종을 칠 때마다 R의 값은 바뀐다.

N명의 사람이 있고, 2019년 12월 31일(TMI: 출제자의 생일임) 밤에 이루어진 제야의 종 타종에서는 총 M번 종을 쳤다고 하자. M번의 타종이 진행되는 동안 사람들은 종소리에 집중하기 위해 움직이지 않는다.

N명의 사람 각각이 각 M번의 타종을 들었는지의 여부가 주어졌을 때, 실제로 가능한 상황인지 판별하여라.

입력

첫 줄에 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 100)이 주어진다.

i+1(1 ≤ i ≤ N)번째 줄에는 M개의 정수 ai,1, ai,2, ..., ai,M 이 주어지는데, ai,j가 1이면 사람 i가 j 번째 타종을 들었음을 의미하고, 0이면 듣지 못했음을 의미한다.

출력

실제로 가능하다면 YES, 아니면 NO를 출력하라.

풀이 및 회고

풀이

DP방식으로 풀이하였다. n x m 사이즈의 DP테이블을 만든다. 이때 DP테이블이 의미하는 것은 종으로 부터의 상대적 거리를 의미한다. i행 j열이 0이라면 dp[i][j] = dp[i - 1][j] + 2, 1이라면 dp[i][j] = dp[i - 1][j] + 1을 해준다. 이 과정에서 만약 i - 1행에서 j열의 값이 j + 1열의 값보다 클 때(j열의 위치가 j + 1열의 위치보다 멀리 위치해있다고 이미 판단한 경우) i행에서 j열의 사람이 들리지만 j + 1열의 사람이 들린다면 불가능한 상황이므로 NO를 출력한다. 마찬가지로 i - 1행에서 j + 1열의 값이 j열의 값보다 클 때 i행에서 j + 1열의 사람이 들리지만 j열의 사람이 들린다면 불가능한 상황이므로 NO를 출력한다.

회고

처음에는 dp테이블 확인차 출력한걸 잘못 출력하는 바람에 틀렸고, 두번째는 숫자를 안 더해주는 바람에.. 뭐 어쩌겠어! 내 잘못인걸?

코드

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * m for _ in range(n)]
possible = True
for i in range(n):
    for j in range(m):
        if not possible:
            break

        if i == 0:
            if a[i][j] == 1:
                dp[i][j] = 1
            else:
                dp[i][j] = 2
            continue

        if j < m - 1:
            if dp[i - 1][j] > dp[i - 1][j + 1]:
                if a[i][j] == 1 and a[i][j + 1] == 0:
                    possible = False
            if dp[i - 1][j] < dp[i - 1][j + 1]:
                if a[i][j] == 0 and a[i][j + 1] == 1:
                    possible = False

        if a[i][j] == 0:
            dp[i][j] = dp[i - 1][j] + 2
        else:
            dp[i][j] = dp[i - 1][j] + 1
print("YES" if possible else "NO")

>> iwtkmn0219의 Github <<