https://www.acmicpc.net/problem/16432
코드
import sys
input = sys.stdin.readline
n = int(input())
arr = []
for _ in range(n):
input_data = list(map(int, input().split()))
arr.append(input_data[1:])
dp = [[[]for _ in range(10)] for _ in range(n)]
for a in arr[0]: # 첫째날
dp[0][a] = [a]
for i in range(1, n):
for a in arr[i]:
for j in range(1, 10):
if a != j and dp[i-1][j] != []:
dp[i][a] = dp[i-1][j]+[a]
break
for i in range(1, 10):
if dp[n-1][i] != []:
for j in range(n):
print(dp[n-1][i][j])
exit()
print(-1)
dp[i][j]는 i번째 날에 j번 떡을 주는 방법을 기록한다. 무슨 말이냐면, 0번째 날에 1번 떡, 1번째 날에 4번떡, 2번째 날에 8번 떡을 주면 dp[2][8]에 저장된 값은 [1, 2, 8]이라는 말이다. 도달할 방법이 없는 칸에는 빈 배열([])이 저장된다.
dp[i][j]의 값은 dp[i-1]의 값들 중 같은 열이 아니면서 빈 배열이 아닌 경우를 갖고와서 j를 배열에 추가해주면 된다.
이렇게 구하여 n-1번째 행에 저장된 값들 중 빈 배열이 아닌 값을 아무거나 출력해주면 된다.
처음에 백트래킹으로 했다가 시간 초과로 다 틀렸다.
20
9 1 2 3 4 5 6 7 8 9
9 1 2 3 4 5 6 7 8 9
9 1 2 3 4 5 6 7 8 9
9 1 2 3 4 5 6 7 8 9
9 1 2 3 4 5 6 7 8 9
9 1 2 3 4 5 6 7 8 9
9 1 2 3 4 5 6 7 8 9
9 1 2 3 4 5 6 7 8 9
9 1 2 3 4 5 6 7 8 9
9 1 2 3 4 5 6 7 8 9
9 1 2 3 4 5 6 7 8 9
9 1 2 3 4 5 6 7 8 9
9 1 2 3 4 5 6 7 8 9
9 1 2 3 4 5 6 7 8 9
9 1 2 3 4 5 6 7 8 9
9 1 2 3 4 5 6 7 8 9
9 1 2 3 4 5 6 7 8 9
9 1 2 3 4 5 6 7 8 9
1 1
1 1
이런 테스트 케이스가 나오면 백트래킹은 8^N번의 연산을 하게 될 수 있기 때문에 당연히 안되는데 생각이 짧았다. 문제의 입력값의 범위를 보고 시간 복잡도를 대략 계산하는 연습을 계속 해야할 것 같다
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 4097번 수익 (1) | 2024.05.15 |
---|---|
[Python/파이썬] 백준 3372번 보드 점프 (0) | 2024.05.11 |
[Python/파이썬] 백준 14430번 자원 캐기 (2) | 2024.04.27 |
[Python/파이썬] 백준 21923번 곡예 비행 (0) | 2024.04.26 |
[Python/파이썬] 백준 15993번 1, 2, 3 더하기 8 (1) | 2024.04.25 |