파이썬 거리두기(goorm level)
📝 풀어보기
문제의 요구사항은 다음과 같다.
조건이 주어질 때, 조건에 따른 스티커를 붙일 수 있는 경우의 수 구하기
먼저 N이 1일때의 테이블에 스티커를 붙일 수 있는 경우의 수를 살펴보자.
# 1은 스티커, 0은 빈 테이블
1. [0, 0, 0]
2. [1, 0, 0]
3. [0, 1, 0]
4. [0, 0, 1]
5. [1, 0, 1]
총 다섯가지가 된다. 즉, 테이블 1줄에 나올 수 있는 경우의 수는 5가지다.
그렇다면 N이 2일때의 테이블에 스티커를 붙일 수 있는 경우의 수를 보자. 2부터는 꽤나 길다.
# 1은 스티커, 0은 빈 테이블
1. [0, 0, 0] 6. [1, 0, 0] 11. [0, 1, 0] 16. [1, 0, 1]
[0, 0, 0] [0, 0, 0] [0, 0, 1] [0, 0, 0]
2. [0, 0, 0] 7. [1, 0, 0] 12. [0, 1. 0] 17. [1, 0, 1]
[1, 0, 0] [0, 1, 0] [1, 0, 1] [0, 1, 0]
3. [0, 0, 0] 8. [1, 0, 0] 13. [0, 0, 1]
[0, 1, 0] [0, 0, 1] [0, 0, 0]
4. [0, 0, 0] 9. [0, 1, 0] 14. [0. 0, 1]
[0, 0, 1] [0, 0, 0] [1, 0, 0]
5. [0, 0, 0] 10. [0, 1, 0] 15. [0, 0, 1]
[1, 0, 1] [1, 0, 0] [0, 1, 0]
위의 배치를 보면 규칙을 하나 찾을 수 있다.
바로 윗 줄의 배치에 따라서 아래줄의 가능한 배치의 수가 정해진다는 점이다.
-
1~5번을 보면 위가 0 0 0일때, 아래는 N=1일때처럼 5가지의 경우의 수가 생긴다.
-
6~8번을 보면 위가 1 0 0일때, 아래는 3가지의 경우의 수가 생긴다.
-
9~11번을 보면 위가 0 1 0일때, 아래는 왼쪽, 오른쪽의 스티커 배치가 가능해지면서 4가지의 경우의 수가 생긴다.
-
13~15번을 보면 위가 0 0 1일때, 아래는 3가지의 경우의 수가 생긴다.
-
16~17번을 보면 위가 1 0 1일때, 아래는 전부 없거나, 중앙만 있거나의 2가지 경우의 수가 생긴다.
이것을 통해 점화식을 생성할 수 있다.
# N*3의 테이블에서 한 줄의 경우의 수는 5가지.
dp = [[0] * 5 for _ in range(N+1)]
# dp[i][j] 값은 i번째 줄의 j번째 테이블에 스티커를 붙이는 경우의 수를 의미
dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][4] # 1번과 같은 5가지 경우의 수
dp[i][1] = dp[i-1][0] + dp[i-1][2] + dp[i-1][3] # 2번과 같은 3가지의 경우의 수
dp[i][2] = dp[i-1][0] + dp[i-1][2] + dp[i-1][3] + dp[i-1][4] # 3번과 같은 4가지의 경우의 수
dp[i][3] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] # 4번과 같은 3가지의 경우의 수
dp[i][4] = dp[i-1][0] + dp[i-1][2] # 5번과 같은 2가지의 경우의 수
-
dp[i][0]의 상태는 바로 위에 어떠한 배치가 있던 간에 상관없이 배치가 가능하다. 그래서 모든 경우를 합한다. -
dp[i][1]의 상태는 가장 왼쪽 테이블에 스티커가 붙어있으므로, 바로 위에 오는 배치에는 왼쪽 테이블에 스티커가 있으면 안된다.이것을 만족하는 배치는
dp[i-1][0],dp[i-1][2],dp[i-1][3]이다. -
dp[i][2]의 상태는 중간 테이블에 스티커가 붙어있다. 바로 위에 오는 배치에는 중간 테이블에 스티커가 있으면 안된다.이것을 만족하는 배치는
dp[i-1][0],dp[i-1][2],dp[i-1][3],dp[i-1][4]가 된다. -
dp[i][3]의 상태는 가장 오른쪽 테이블에 스티커가 붙어있으므로, 바로 위에 오는 배치에는 오른쪽 테이블에 스티커가 있으면 안된다.이것을 만족하는 배치는
dp[i-1][0],dp[i-1][1],dp[i-1][2]가 된다. -
dp[i][4]의 상태는 가장 왼쪽과 오른쪽 테이블에 스티커가 붙어있으므로, 바로 위에 오는 배치에는 왼쪽과 오른쪽 테이블에 스티커가 있으면 안된다.이것을 만족하는 배치는
dp[i-1][0],dp[i-1][2]가 된다.
이제 세운 점화식을 100_000_007의 값으로 나눈 나머지를 저장하고 dp[N]의 값을 모두 합한 값을 100_000_007으로 나눈 나머지를 출력하면 된다.
전체코드
N = int(input())
dp = [[0] * 5 for _ in range(N+1)]
dp[0][0] = 1 # 초기값 설정
mod = 100_000_007
for i in range(1, N+1):
dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3] + dp[i-1][4]) % mod
dp[i][1] = (dp[i-1][0] + dp[i-1][2] + dp[i-1][3]) % mod
dp[i][2] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][3] + dp[i-1][4]) % mod
dp[i][3] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % mod
dp[i][4] = (dp[i-1][0] + dp[i-1][2]) % mod
print(sum(dp[N]) % mod)
DP문제는 도출되는 코드의 길이에 비해, 문제를 파악하고 점화식을 구상 하는데에 많은 시간과 생각을 필요로 하는것 같다.
항상 이러한 유형의 문제에서 부족함이 많다는것을 느낀다.
이 문제의 해설은 아래와 같다.
해설
N = int(input())
dp = [[0 for _ in range(5)] for _ in range(N + 1)]
dp[0][0] = 1
MOD = 100000007
for i in range(1, N + 1):
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][4]) % MOD
dp[i][1] = (dp[i - 1][0] + dp[i - 1][2] + dp[i - 1][3]) % MOD
dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][3] + dp[i - 1][4]) % MOD
dp[i][3] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD
dp[i][4] = (dp[i - 1][0] + dp[i - 1][2]) % MOD
print(sum(dp[N]) % MOD)
해설2
import sys
sys.setrecursionlimit(150000)
# 이 정해 코드를 그냥 실행하면 스택 메모리 제한으로 인해 일부 테스트 케이스를 통과하지 못합니다.
# 아래 주석 처리된 코드와 같이 실행하면, 스택 메모리 제한을 임시적으로 조금 늘려서 문제를 해결할 수 있습니다.
# 시스템에 직접 접근하는 코드이므로, 일반적으로 코딩 테스트를 응시할 때는 사용하면 안되는 코드입니다!!
import resource
resource.setrlimit(resource.RLIMIT_STACK, (64 * 1024 * 1024, -1))
MOD = 10**8 + 7
N = int(input())
dp = dict()
for n in range(5):
dp[(0, n)] = 1 if n == 0 else 0
def get(i, n):
if (i, n) in dp:
return dp[(i, n)]
ret = 0
if n == 0:
ret += get(i - 1, 0) + get(i - 1, 1) + get(i - 1, 2) + get(i - 1, 3) + get(i - 1, 4)
elif n == 1:
ret += get(i - 1, 0) + get(i - 1, 2) + get(i - 1, 3)
elif n == 2:
ret += get(i - 1, 0) + get(i - 1, 1) + get(i - 1, 3) + get(i - 1, 4)
elif n == 3:
ret += get(i - 1, 0) + get(i - 1, 1) + get(i - 1, 2)
else:
ret += get(i - 1, 0) + get(i - 1, 2)
ret %= MOD
dp[(i, n)] = ret
return ret
ans = 0
for n in range(5):
ans += get(N, n)
print(ans % MOD)