HUFS/2021 HUFS 모각코 캠프
[모각코] 210728 Today I Learned
sohy
2021. 7. 30. 02:38
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
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 라는데,, 원인을 모르겠다. 알고리즘 자체가 잘못됐나 ㅜ 다시 생각해봐야겠다.
