문제 : https://www.acmicpc.net/problem/2591
초기 구상과정
- DP : 작은 것을 구상하여 큰 문제를 해결하는 방법
- '숫자를 하나하나 입력 받진 않지만 하나의 숫자가 들어오면 분명 규칙있게 숫자들이 만들어지고 경우의 수가 나누어질 것이다.'고 생각했고 그 규칙을 찾는 것에 대해서 집중하였다.
- 숫자가 들어오면 그 전 숫자와 두자리로 붙이던지 따로 한 개의 숫자로 만들어서 생각할 것인지 결정하여 타당성을 따져봐야한다.
- 이런 식에서 규칙들을 찾아서 조건 분기를 하여 dp 리스트를 생성하면 답을 찾을 수 있다.
- dfs로 풀면 시간 초과 땅.땅.땅.
초기 코드
import sys
input = sys.stdin.readline
nums = list(input().rstrip())
grand = ''
parent = ''
num = ''
dp = [0] * len(nums)
# dp 초기값 설정
dp[0] = 1
if nums[1] == '0':
dp[1] = 1
else:
dp[1] = 2
for i in range(2, len(nums)):
grand = nums[i - 2]
parent = nums[i - 1]
num = nums[i]
if int(num) == 0 and int(parent) == 0 or int(num) == 0 and int(parent) > 3:
break
elif 0 < int(parent) <= 3 and int(num) == 0:
dp[i] = dp[i - 1] - 1
elif int(grand + parent) <= 34 and int(parent + num) <= 34:
dp[i] = dp[i - 2] + dp[i - 1]
elif int(grand + parent) <= 34 and int(parent + num) > 34:
dp[i] = dp[i - 1]
elif int(grand + parent) > 34 and int(parent + num) <= 34:
dp[i] = dp[i - 2] * 2
elif int(grand + parent) > 34 and int(parent + num) > 34:
dp[i] = dp[i - 2]
print(dp[len(nums) - 1])규칙을 풀어나가다보니 자꾸 전전 숫자도 찾아봐야하는 것 같아서 세가지 숫자를 저장해서 분기를 했다. 그런데 왜, 왜 때문에 틀리는 거죠??????
dp[i] = dp[i - 2] or dp[i] = dp[i - 1] 두 개 다 수정하고 문제들을 살펴보는대도 자꾸 틀린다. 왜 그럴까? 정말 나한테 왜 그럴까? 하하하하하하하하하하
중간 코드
for i in range(2, len(nums)):
grand = nums[i - 2]
parent = nums[i - 1]
num = nums[i]
if int(num) == 0 and int(parent) == 0 or int(num) == 0 and int(parent) > 3:
break
elif int(num) == 0 and 0 < int(parent) <= 3:
dp[i] = dp[i - 2]
elif int(parent) == 0:
dp[i] = dp[i - 1]
elif int(grand + parent) <= 34 and int(parent + num) <= 34:
dp[i] = dp[i - 2] + dp[i - 1]
elif int(grand + parent) <= 34 and int(parent + num) > 34:
dp[i] = dp[i - 1]
elif int(grand + parent) > 34 and int(parent + num) <= 34:
dp[i] = dp[i - 2] + dp[i - 1]
elif int(grand + parent) > 34 and int(parent + num) > 34:
dp[i] = dp[i - 1]
print(dp[len(nums) - 1])자세히 또 다시 규칙들을 찾으면서 조건 분기를 했더니 사소하게 생각하고 다른 케이스들을 생각하지 않고 섣부르게 일반화를 한 부분들이 있었다. 그저 -1이 되는 것이 아닌 그 전 케이스까지 연관되어 만들어진 점화식이었는데 그 부분들을 간과하고 만들었던 것이다. 드디어 깨달았다!
근데 왜 아직까지도 틀렸다는 거죠? 나한테 왜 그러는거죠? 나 뭐 잘못한거죠? 다 해줬잖아..
최종코드
결국 조건 분기를 다시 해보았다. 결정적으로 세 개의 숫자를 가지고 장난을 칠 필요가 없었다. 숫자는 34까지이기 때문에 숫자 두 개로 지지고 볶고 조건분기를 찾아보면 되는 것이었다.
import sys
input = sys.stdin.readline
nums = list(input().rstrip())
grand = ''
parent = ''
num = ''
dp = [0] * len(nums)
# dp 초기값 설정
dp[0] = 1
if (nums[1] != '0' and 1 <= int(nums[0]) < 3) or (nums[0] == '3' and 1 <= int(nums[1]) <= 4):
dp[1] = 2
else:
dp[1] = 1
for i in range(2, len(nums)):
grand = nums[i - 2]
parent = nums[i - 1]
num = nums[i]
if int(num) == 0 and int(parent) == 0 or int(num) == 0 and int(parent) > 3:
break
elif int(num) == 0 and 0 < int(parent) <= 3:
dp[i] = dp[i - 2]
elif int(parent) == 0:
dp[i] = dp[i - 1]
elif int(parent + num) <= 34:
dp[i] = dp[i - 2] + dp[i - 1]
elif int(parent + num) > 34:
dp[i] = dp[i - 1]
print(dp[len(nums) - 1])기존에 찾았던 내용과 크게 다를것이 없었지만 두 개의 숫자로 조건을 분기해서 더 많은 케이스들을 찾아낼 수 있었고 훨씬 더 규칙성이 눈에 두드러졌다.
느낀점
조건 분기를 많이해서 자세하게 나누면 정밀하게 정보를 처리하고 내가 원하는 내용을 도출시키는데 더 좋을 것이라고 생각했던 내가 바보였다. 과유불급이라는 말을 잊지 말고 적절한 분기를 통해서 처리해야 하는 것만 딱딱 찾아서 하는 것이 좋다. 또한, 너무 멀리 돌아왔다고 느끼면 다시 제자리로 돌아가서 문제를 해결하는 것도 도움이 많이 된다는 점을 알자. 이번처럼 한 문제로 하루 절반을 쓰지말구 (제발..)
