[백준] 2780 비밀번호 (파이썬 Python)

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

2780번: 비밀번호

문제 설명

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

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

1. 비밀번호의 길이는 N이다.
2. 비밀번호는 위 그림에 나온 번호들을 눌러서 만든다.
3. 비밀번호에서 인접한 수는 실제 위 기계의 번호에서도 인접해야 한다.

 (ex. 15 라는 비밀번호는 불가능하다. (1과 5는 인접하지 않는다. ) 하지만 1236이라는 비밀번호는 가능하다.)

---

풀이 과정

• 나의 풀이

① 이 문제에서 직관적으로 파악한 것은 '직감적으로 DP문제 느낌이 나지만... 예제를 분석해보며 DP문제인지 아닌지 한번 더 확인해봐야겠다..!'이다.

② 아이디어 열기

(1) 예제 분석하기(n : 비밀번호의 길이)

  n = 1 ; 10가지 (0~9가 하나씩 선택되는 경우)

  n = 2 ; 26가지 (07,78,74.....)

  n = 3 ; 74가지 (078,074....)

  n이 1인 경우는 쉽게 눈으로 구할 수 있었지만 n이 2인 경우부터는 시작을 0으로부터해서 비밀번호의 길이가 2인 경우 세기, 시작을 1로부터해서 비밀번호의 길이가 2인 경우 세기...로 나만의 기준을 만들었다.

  그 결과 나만의 간단한 규칙을 찾았다.

● n=3인 경우를 살펴보자. 

  시작을 0부터 한다면.... 2번째 숫자로는 7밖에 올 수가 없고 사실상 그러면 7부터 시작하는 비밀번호의 길이가 2인 경우의 수와 같아진다.

  만약 5부터 시작한다면, 2번째 숫자로 올 수 있는 수는 2,4,6,8이고 사실상 그러면 5부터 시작하는 비밀번호의 길이가 3인 경우는 숫자가 2,4,6,8로 시작하며 비밀번호의 길이가 2인 경우의 수와 같다. 

 

 이를 일반화하여 점화식의 형태로 나타내면 다음과 같다. (f는 구하고자하는 값이고 f-1은 이전값)

첫번째로 선택될 숫자가 0 : f(0) = f-1(7)

첫번째로 선택될 숫자가 1 : f(1) = f-1(2) + f-1(4)

첫번째로 선택될 숫자가 2 : f(2) = f-1(1) + f-1(3) + f-1(5)

첫번째로 선택될 숫자가 3 : f(3) = f-1(2) + f-1(6) 

첫번째로 선택될 숫자가 4 : f(4) = f-1(1) + f-1(5) + f-1(7) 

첫번째로 선택될 숫자가 5 : f(5) = f-1(2) + f-1(4) + f-1(6) + f-1(8) 

첫번째로 선택될 숫자가 6 : f(6) = f-1(3) + f-1(5) + f-1(9) 

첫번째로 선택될 숫자가 7 : f(7) = f-1(4) + f-1(8) + f-1(0) 

첫번째로 선택될 숫자가 8 : f(8) = f-1(5) + f-1(7) + f-1(9) 

첫번째로 선택될 숫자가 9 : f(9) = f-1(6) + f-1(8) 

 

(2) 코드 구현

 내가 직접 구한 방법을 코드로 구현하면 다음과 같다.

# 2780 비밀번호
import sys
input = sys.stdin.readline
T = int(input())

for i in range(T) :
    n = int(input())
    num = [1]*10
    for j in range(1,n) :
        num0 = num[0]
        num1 = num[1]
        num2 = num[2]
        num3 = num[3]
        num4 = num[4]
        num5 = num[5]
        num6 = num[6]
        num7 = num[7]
        num8 = num[8]
        num9 = num[9]

        num[0] = num7
        num[1] = num2 + num4
        num[2] = num1 + num3 + num5
        num[3] = num2 + num6
        num[4] = num1 + num5 + num7
        num[5] = num2 + num4 + num6 + num8
        num[6] = num3 + num5 + num9
        num[7] = num4 + num8 + num0
        num[8] = num5 + num7 + num9
        num[9] = num6 + num8

    print(sum(num)%1234567)

  일단 테스트케이스만큼 for문을 돌리고, 발견한 규칙대로 코드를 구현해줬다.

  결과는...!

 성공-!-!

---

후기

  규칙이 쉽게 보여서 다행이었다...!!