백준 : 9095 - 1, 2, 3 더하기

점화식으로 풀면 금방 푼다고 하는데, 점화식 자체를 이해하는데 한 시간이 걸렸다.. 손으로 다 써보니까 점화식이 무슨 말인지 이해가 간다.

점화식의 풀이 과정을 다 써본 바로는 저렇게 나온다.

 

dp(6) = dp(5) + dp(4) + dp(3) 을 정규식으로 바꾸면 다음과 같이 풀 수 있다.

 

dp(n) = dp(n-1) + dp(n-2) + dp(n-3)

dp(6) 까지 가는 과정에 대한 손풀이

 

문제에서 n은 11이하의 양수라고 주어졌기에, 우선 리스트에 모든 가능한 dp값을 채워넣는 방식으로 접근했다. 그리고 a의 값에 따라, b 리스트에서 해당하는 인덱스의 값을 반환하도록 하였다. 만약, 값이 커진다면 재귀 함수를 이용한 풀이가 필요할 것으로 보인다.

n = int(input())
a = [int(input()) for __ in range (n)]
b = [1, 2, 4]
count = 0
for a in a:
    if a <= 3 :
        print(b[a-1])
    if a > 3 : 
        for j in range (3, 12):
            num = b[j-1] + b[j-2] + b[j-3]
            b.append(num)
        print(b[a-1])

 

---

오늘로 한 가지 확실해진것은, 내가 어려워 하는 것은 인덱스를 설정하는 부분이다. 이 코드를 작성하면서 에러를 봤던 부분은 다음과 같다.

1. if a ≤ 3 부분에서 같을때를 고려하지 않고 하여, 반례 사이트에서 3이 들어간 예제에서 모두 틀린 값을 반환하는 것을 확인했다.
2. for j in range (3, 12) 부분에서 b의 리스트 값을 3으로 설정해둬야 한다는 점이다. 처음에는 4로 설정해서 b[j-1] 부분에서 인덱싱 에러가 발생했다. 왜냐햐면 b[3] = 4로 마지막 값이다. 첫 인덱스는 0으로 시작하는것을 모르는 부분이 아닌데도 항상 놓치면서 동일한 에러를 계속 보는 것으로 보인다.

운영진 티타임에서 정민 서브코치님이 말씀하신 것과 같이, 아직 컴퓨터처럼 사고하지 못하여 휴먼 에러를 반환하는 것으로 보인다. 나름 친해졌다 생각했는데 컴퓨터와 더 친해져야 하나보다.

 

소심한 분노