[백준 2193번] 이친수 - python

https://www.acmicpc.net/problem/2193

📌 문제 탐색하기

목표

• 0으로 시작하지 않고, 1이 두 번 연속으로 나타나지 않는 이친수의 개수를 구한다.

입력값

• 첫 줄에 자릿수를 나타내는 n을 입력한다. (1 ≤ N ≤ 90)
• ex)
• 3

출력값

• n자리 이친수의 개수를 출력한다.
• ex)
• 2

📌 코드 설계하기

해결 아이디어

• 가장 처음으로 해야될게 입력된 정수를 binary로 바꿔야하는 것이다. 파이썬에 이렇게 이진수로 바꾸는 함수가 있나.?
• 이진수로 바꿔서 코드를 작성했더니 시간 초과가 떴다.
• 그러면 규칙을 찾아야한다. 이진수는 계속 반복된다. dp를 사용할 수는 없을까?

📌 1차 제출 코드

import sys

input = sys.stdin.readline

n = int(input().strip())
cnt = 0

for i in range (pow(2,n)):
    i = str(bin(i)).split('b')[-1]
    i = i.zfill(n)
    if i[0] != '0' and '11' not in i:
        cnt+= 1

print(cnt)

• 시간 초과가 떴다. pow(2, n)을 해버리니 개수가 $2^n$으로 개수가 늘어버려서 n이 90일 때 $2^{90}$이라.. 그렇다..ㅎ..
• 이 방법은 버린다!

📌 정답 코드

import sys

input = sys.stdin.readline

n = int(input().strip())
dp = [0] * (n+1)
dp[1] = 1

for i in range (2, n+1):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n])

시간 복잡도

• for문이 한 번 돌기 떄문에 O(N)이 된다.

입출력 시간 단축하기

input = sys.stdin.readline print = sys.stdout.write

📌 Trouble Shooting

1. 입출력 속도 줄이기

import sys

input = sys.stdin.readline
print = sys.stdout.write

n = int(input().strip())
print(str(bin(n)))

• 일단 binary로 바꿔보자는 생각에 이렇게 코드를 짰다. 근데 결과가 ‘0b101%’ 이렇게 출력이 됐다. 마지막에 %가 뭐지?
• print() 함수는 기본적으로 끝에 개행을 붙여준다. 하지만 sys.stdout.write()는 문자열 그대로만 출력한다. 따라서 출력 끝에 줄바꿈이 없으면 %기호를 붙여서 시작적으로 마지막이라는 것을 표시해준다고 한다.
• 따라서 출력 뒤에 \n을 직접 붙여서 해당 기호를 제거할 수 있다. 아래처럼!

import sys

input = sys.stdin.readline
print = sys.stdout.write

n = int(input().strip())
print(f"{bin(n)}\\n")

1. 파이썬 자릿수 맞추기

i = i.zfill(n)

• zfill(): 문자열 앞에 0을 채우는 함수이다.
• rjust(): 문자열 앞에 0말고 다른 것들을 채울 수 있다.
• i = i.rjust(2, 'a') // i를 두자릿수로 만들도록 하고 이를 맞추기 위해 앞에 문자 a를 채운다.