[모각코] 210728 Today I Learned

2193번: 이친수 (acmicpc.net)

2193번: 이친수

 

N = int(input())
pinary = [0 for i in range(N)]

for i in range(1, N):
    if i == 1:
        pinary[i] = (1, 0)  # (0으로 끝나는 문자열 개수, 1로 끝나는 문자열 개수)
    else:
        pinary[i] = (pinary[i-1][0] + pinary[i-1][1], pinary[i-1][0])

print(int(pinary[-1][0]) + int(pinary[-1][1]))

 

0으로 끝난 문자열은 자릿수가 하나 더 추가됐을 때 2개의 문자열을 만들 수 있고, 1로 끝난 문자열은 1개의 문자열을 만들 수 있다. 0으로 끝난 문자열 다음엔 0과 1 모두 올 수 있고, 1로 끝난 문자열엔 0만 올 수 있기 때문이다.

예를 들어, 3 자릿수 문자열은 100, 101 두 가지인데 여기에 자릿수 하나를 더 추가하면 100 다음으로는 0과 1 둘 다 올 수 있고, 101 다음으로는 0만 올 수 있다. 따라서 4 자릿수 문자열은 1000, 1001, 1010 로 3가지가 된다.

그래서 나는 0으로 끝나는 문자열과 1로 끝나는 문자열 개수를 튜플로 (0으로 끝나는 문자열 개수, 1로 끝나는 문자열 개수) 저장해오다가 마지막 N자리에 도달했을 때 그 두 개를 합하는 알고리즘을 생각했다. 0으로 끝나는 문자열 개수는 이전의 문자열 총 개수가 되고, 1로 끝나는 문자열 개수는 0으로 끝난 문자열 개수가 된다. 

이렇게 했을 때 vs code에서는 잘 나오는데 백준에서 런타임 에러가 난다 ㅜㅜ type error 라는데,, 원인을 모르겠다. 알고리즘 자체가 잘못됐나 ㅜ 다시 생각해봐야겠다.

 

아오 ㅡㅡ