[백준-파이썬] 2591: 숫자카드

문제 보러 가기!!

TMI로 시작하는 서론

이 문제는 전에 풀었던 포도주 시식 문제와 비슷한 식으로 풀었다..! 그 문제는 어떻게 풀어야 할지 잘 모르겠어서, 친구에게 물어봐서 풀었다.
포도주 시식 백준 문제 보러가기~
벨로그에 올린 문제풀이 보러가기!
그러다 이를 활용해서 숫자카드를 혼자서 푸니 너무 뿌듯하고 기분이 좋아서 벨로그에 글을 쓴다 ㅎㅎ 😍

아이디어, 설명

2차원 리스트를 활용해서 풀었는데 말보다 그림이 더 이해가 잘 될 것 같아서, 그림을 올린다..!

숫자를 문자열로 받아서 인덱스로 하나 하나 본다.

2차원 리스트 dp의 열은 각각 인덱스의 숫자를 1자리로 표현할 때 경우의 수 누적, 이전 인덱스의 숫자와 해당 인덱스의 숫자를 2자리 카드로 표현할 때 경우의 수 누적을 의미한다. 행은 각각 인덱스의 숫자들을 뜻한다.

dp[0][0] 즉, 첫번째 숫자를 1자리 카드로 표현할 때 경우의 수 누적은 1이다.
dp[0][1] 즉, 첫번째 숫자와 그 전 숫자를 2자리 카드로 표현할 때 경우의 수 누적은 0이다. 첫번째 숫자니까.. 그 이전 숫자가 없으니까 2자리 카드로 표현하는 것 자체가 불가능하다. 이 두 개는 먼저 넣어줬다.

그리고 문자열 인덱스 1부터 끝까지 살펴본다.
먼저 이전 인덱스, 해당 인덱스의 숫자를 가지고 2자리 숫자로 만들었을 때.. 예를 들면 '3', '5'를 숫자 35로 보는 것이다. 그게 10~34이면, 두 자리수 카드로 표현할 수 있는 것이다. 이전 인덱스의 숫자는 1자리로 표현되었을 때 경우의 수를 그대로 가져오면 되겠다고 생각했다.

이전 인덱스의 숫자와 이전의 이전 인덱스 숫자가 2자리로 표현되었을 때의 경우의 수는 안 가져와야 한다! 뭔가 설명이 이해가 잘 안될 것 같아서 예시를 써본다.
그림에서 인덱스 4을 보자. 그때 이전 인덱스의 숫자 2과 해당 인덱스의 숫자 3은 '23'이 된다. 그럼 두 자리수 카드로 표현할 수 있다. 그런데 만약 이전 이전 인덱스 숫자(인덱스-2, 숫자-1), 이전 인덱스 숫자(인덱스-3, 숫자-2)가 2자리로 표현되었을 때 (12) 경우까지 가져와버리면... 카드 한장에 '123'이 되는 경우를 고려하는 것이다. 그래서 dp[1][i] = dp[0][i-1]을 했다.

그리고 해당 인덱스의 숫자가 0이라면 continue를 해버린다. 우리에게는 숫자카드 0은 없으니까.. 단독으로 표현할 수 없다. 만약에 해당 인덱스의 숫자가 1~9라면, 단독으로도 표현할 수 있다. 그 때의 경우는 수는 이전 인덱스 숫자를 1자리 카드로 표현했을 때와 이전 인덱스 숫자를 (이전의 이전 인덱스 숫자와 함께) 2자리 카드로 표현했을 때를 더해야 한다.

만약에 숫자가 123이 있다고 생각해보겠다.
해당 인덱스가 2라고 생각해보자. 그러면 숫자 3이다.

1) 이전 인덱스의 숫자(인덱스-1, 숫자-2)를 1자리 카드로 표현했을 때
1 2 3
2) 이전 이전 인덱스(인덱스-0, 숫자-1), 이전 인덱스(인덱스-1, 숫자-2)의 숫자를 2자리 카드로 표현했을 때
12 3

마지막 인덱스까지 계산한 후에, dp[0][n-1]과 dp[1][n-1]을 더하면 정답이다! 마지막 인덱스의 숫자를 1자리 카드로 표현했을 때, 그 이전 인덱스의 숫자와 함께 2자리 카드로 표현했을 때를 더하니까~!

코드 👩‍💻

cards = input()
n =len(cards)
dp = list([0]*(n) for _ in range(2)) # 열은 숫자카드에 숫자가 1자리인지, 2자리인지. 행은 각각 숫자를 보면서, 그 숫자까지 몇 개의 숫자 카드로 구성할 수 있는지
dp[0][0] = 1 # 처음 숫자는 당연히 1자리만 있고, 1개의 숫자카드로 만들 수밖에 없으니까
dp[0][1] = 0 # 처음 숫자는 2자리가 될 수 없으니까

for i in range(1, n):
    if 10 <= int(cards[i-1:i+1]) <= 34: # 해당 숫자와 그 앞자리 숫자를 보면서, 이게 두 자리수짜리 카드로 표현 가능하다면
        dp[1][i] = dp[0][i-1]

    if cards[i] == '0': # 해당 숫자가 0이라면, 단독으로 표현 불가능하니까
        continue

    dp[0][i] = dp[0][i-1] + dp[1][i-1] # 해당 숫자가 1~9라서 단독으로 표현하는 경우


print(int(dp[0][n-1]) + int(dp[1][n-1]))