[백준/2780] 비밀번호(Python)

Problem : https://www.acmicpc.net/problem/2780

2780번: 비밀번호

 

Difficulty : Silver 1

 

Status : Solved

 

Time : 00:05:21

 

---

 

문제 설명

 

 

석원이는 자신의 현관문에 비밀번호 기계를 설치했다. 그 기계의 모양은 다음과 같다.

지나가던 석원이 친구 주희는 단순한 호기심에 저 비밀번호를 풀고 싶어한다. 이때 주희는 바닥에 떨어져 있는 힌트 종이를 줍게 된다. 이 종이에는 석원이가 비밀번호를 만들 때 사용했던 조건이 적혀 있다. 이제 주희는 이 조건을 가지고, 석원이 집의 가능한 비밀번호의 전체 개수를 알고 싶어 한다. 현재 컴퓨터를 사용할 수 없는 주희는 당신에게 이 문제를 부탁했다. 석원이의 힌트 종이는 다음과 같다.

비밀번호의 길이는 N이다.
비밀번호는 위 그림에 나온 번호들을 눌러서 만든다.
비밀번호에서 인접한 수는 실제 위 기계의 번호에서도 인접해야 한다.
(ex. 15 라는 비밀번호는 불가능하다. (1과 5는 인접하지 않는다. ) 하지만 1236이라는 비밀번호는 가능하다.)

 

 

입력 및 출력

 

입력

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 비밀번호의 길이 N이 주어진다.( 1 <= N <= 1,000 )

 

출력

각각의 Test case에 대해서 조건을 만족하는 비밀번호의 개수를 출력하라. 단, 수가 매우 커질 수 있으므로 비밀번호의 개수를 1,234,567으로 나눈 나머지를 출력하라.

 

입력 예시

3
1
2
3

 

출력 예시

10
26
74

 

 

---

 

풀이

 

단순히 브루트포스로 풀려면 최대 10^1000의 경우의 수를 모조리 테스트해보아야 한다. 즉 탈락.

 

이 문제는 DP를 통해 접근해 보도록 하자.

 

현재 암호 길이가 i, 그리고 마지막 자리 숫자가 j인 경우의 수를 dp[i][j]라고 두면, j번째 수와 인접한 모든 수(상하좌우 최대 4가지)에 모두 dp[i][j]를 더해 줄 수 있다. 즉 상하좌우의 수 k에 대해 dp[i+1][k] += dp[i][j]가 가능하다. 이를 ㅑ == 1000까지 먼저 구해준 후, 모든 테스트케이스에 대해 경우의 수의 총합을 출력하면 끝.

 

 

풀이 코드

import sys
input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
pad = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
  [0, -1, -1]
]
MOD = 1234567
MAX = 1001
dp = [[0]*10 for _ in range(MAX)]

for i in range(10) :
  dp[1][i] = 1

for i in range(1, MAX-1) :
  for j in range(10) :
    if j == 0:
      x, y = 0, 3
    else :
      x, y = (j-1) % 3, (j-1) // 3

    for k in range(4) :
      ax, ay = x + dx[k], y + dy[k]
      if -1 < ax < 3 and -1 < ay < 4 and pad[ay][ax] > -1 :
        dp[i+1][pad[ay][ax]] = (dp[i+1][pad[ay][ax]] + dp[i][j]) % MOD

T = int(input())
for _ in range(T) :
  n = int(input())
  print(sum(dp[n]) % MOD)

풀이 완료!