파이썬 거리두기(goorm level)


스크린샷 2023-05-18 오후 2 34 41 스크린샷 2023-05-18 오후 2 34 55 스크린샷 2023-05-18 오후 2 35 06


📝 풀어보기

문제의 요구사항은 다음과 같다.

조건이 주어질 때, 조건에 따른 스티커를 붙일 수 있는 경우의 수 구하기

먼저 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. 1~5번을 보면 위가 0 0 0일때, 아래는 N=1일때처럼 5가지의 경우의 수가 생긴다.

  2. 6~8번을 보면 위가 1 0 0일때, 아래는 3가지의 경우의 수가 생긴다.

  3. 9~11번을 보면 위가 0 1 0일때, 아래는 왼쪽, 오른쪽의 스티커 배치가 가능해지면서 4가지의 경우의 수가 생긴다.

  4. 13~15번을 보면 위가 0 0 1일때, 아래는 3가지의 경우의 수가 생긴다.

  5. 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가지의 경우의 수
  1. dp[i][0]의 상태는 바로 위에 어떠한 배치가 있던 간에 상관없이 배치가 가능하다. 그래서 모든 경우를 합한다.

  2. dp[i][1]의 상태는 가장 왼쪽 테이블에 스티커가 붙어있으므로, 바로 위에 오는 배치에는 왼쪽 테이블에 스티커가 있으면 안된다.

    이것을 만족하는 배치는 dp[i-1][0], dp[i-1][2], dp[i-1][3]이다.

  3. dp[i][2]의 상태는 중간 테이블에 스티커가 붙어있다. 바로 위에 오는 배치에는 중간 테이블에 스티커가 있으면 안된다.

    이것을 만족하는 배치는 dp[i-1][0],dp[i-1][2],dp[i-1][3],dp[i-1][4]가 된다.

  4. dp[i][3]의 상태는 가장 오른쪽 테이블에 스티커가 붙어있으므로, 바로 위에 오는 배치에는 오른쪽 테이블에 스티커가 있으면 안된다.

    이것을 만족하는 배치는 dp[i-1][0], dp[i-1][1],dp[i-1][2]가 된다.

  5. 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)

관심있을 포스팅