2193번 이친수

·2021년 1월 22일
0

PS

목록 보기
5/42

문제 출처 : https://www.acmicpc.net/problem/2193

동적 계획법인지 의식도 못할정도로 동적 계획법을 이용하면 간단히 풀리는 동적계획법의 기초문제

풀이 1.

입력값을 나열해보고 N자리 이친수의 개수가 어떻게 결정되는지 살펴보니 문제의 조건에 의해 다음과 같이 조건이 변형된다.

1. N자리에서 0으로 끝나는 이친수에 의해 N+1자리에서는 두 개의 이친수( 0으로 끝나는, 1로 끝나는 수)가 추가로 생성된다.]
2. N자리에서 1로 끝나는 이친수에 의해 N+1자리에서는 한 개의 이친수 ( 0으로 끝나는 수 )가 추가로 생성된다.
3. 모든 이친수는 10XXX...로 시작되어야 한다. ( 1자리수( =1) 제외 ) 

이를 바탕으로 N+1자리의 이친수의 개수를 N자리의 이친수의 개수로 저장하는 동적 계획법을 완성할 수 있다.

import sys

N = int(sys.stdin.readline().rstrip("\n"))

pinary = [[0,0] for _ in range(N+1)]
pinary[1][0],pinary[1][1] = 0,1

for i in range(2,N+1) :
    pinary[i][0] = pinary[i-1][0]+pinary[i-1][1]
    pinary[i][1] = pinary[i-1][0]

print(pinary[N][0]+pinary[N][1])

풀이 2.

다른 사람들의 정답은 나보다 시간복잡도가 조금 더 빠르다. 그래서 더 빨리 종료되는 코드를 찾아보려고 생각했다. 이전에 이것과 비슷한 문제 (01타일 이였나)에서처럼 사실 단순히 결과값만 가지고도 문제를 해결할 수 있다. (이것도 일종의 DP라고 하면 DP인가 N자리 이친수의 개수가 N-1, N-2자리의 이친수의 개수에 의해 결정되니까... )

import sys

N = int(sys.stdin.readline().rstrip("\n"))

pinary=[0 for _ in range(N+1)]
pinary[1]=1
for n in range(2,N+1) :
    pinary[n]=pinary[n-1]+pinary[n-2]
print(pinary[N])

근소하게나마 시간이 감소했다.


추가로...

어떤 분이 진짜 짧게 풀었길래 도저히 안될것 같아서 궁금해서 참고하고자 봤는데...

a=1
b=1
n=int(input())
for i in range(n-1):
   a,b=b,a+b
print(a)

이건 뭐지...? for문 안에 있는 저런 라인은 처음 보는데 역할이 뭔지 찾아봐야겠다.

profile
세상은 너무나도 커

0개의 댓글