알고리즘

[백준] 2193 이친수 - 실버 3

swanzzz 2025. 5. 18. 19:42
반응형

[오늘의 문제]

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

[오늘의 학습 키워드]

  • DP, 구현

1. 문제설명

[제한사항]

  • 시간 제한 2초
  • 메모리 제한 128MB
  • 1 ≤ N ≤ 90

2. 접근방식

이 문제는 0과 1로 이루어진 이친수를 구성하는 방식을 잘 생각해야 하는 문제입니다.

 

이친수는 1로만 시작하고 1이 연속할 수 없다는 특징이 있습니다.

 

그렇다면 이친수가 가능한 조건은 1로 시작한 수 중에서 1이 연속하지 않는다면 모두 이친수가 된다는 의미이죠

 

N 이 1이 주어졌다면 이친수가 될 수 있는 수는 1 뿐이고

2가 주어진다면 10

3이 주어진다면 100, 101

4가 주어진다면 1000, 1001, 1010

 

이런식으로 되겠죠 여기서 구할 수 있는 점화식은 0과 1의 개수를 다르게 보아야 한다는 것입니다.

이 그림을 보면 좀더 이해가 쉬울 것 같습니다.

 

앞서 수가 0으로 끝난다면 그 뒤에 올 수 있는 수는 1과 0이 올 수 있습니다.

1로 끝났다면 올 수 있는 수는 0 뿐이죠

 

즉 다음 이친수의 0의 개수는 기존의 0의 개수에 1의 개수만큼 늘어나죠

 

왜냐하면 1뒤에 0이 오기 때문에 기존 1의 개수가 0의 개수가 되기 때문입니다.

반대로 1의 개수는 0만큼 늘어납니다.

 

0뒤에 올 수 있는 수가 0과 1이 존재하기 때문에 1의 개수는 기존의 0의 개수만큼 늘어납니다.

 

이를 코드로 세워보면 이렇게 되겠죠

DP[i][0] = DP[i - 1][0] + DP[i - 1][1]
DP[i][1] = DP[i - 1][0]

3. 코드

import sys
input = sys.stdin.readline

N = int(input())
DP = [[0] * 2 for _ in range(N + 1)]

# 0의 개수, 1의 개수
DP[1][0] = 0
DP[1][1] = 1

# 점화식 채워주기
for i in range(2, N + 1):
    DP[i][0] = DP[i - 1][0] +  DP[i - 1][1]
    DP[i][1] = DP[i - 1][0]

print(sum(DP[N]))

[코드설명]

제한 사항을 보면 N이 1부터 최대 90까지 주어진다고 되어 있습니다.


따라서 생성한 DP 테이블을 초기화 하는 수는 1까지만 해주어야 하는데, N이 1인 경우 올 수 있는 수는 1 뿐이죠

1은 0으로 끝난 개수 0개, 1로 끝난 개수 1개와 동일합니다.

 

따라서 이렇게 초기화를 실시해주고 2부터 전체 탐색을 실시하며 DP 테이블을 채워 나갑니다.

 

이렇게 채우면 2의 경우 0의 개수는 0의 개수 + 1의 개수 이니 총 1이 되고

1의 개수는 0의 개수이니 0으로 2는 총 1이 됩니다.

 

3은 이렇게 하면 1, 1 로 총 2가 되겠죠

4. 결과

[회고]

확실히 쉬운 문제 였습니다.

 

DP 필수 문제집을 풀며 점화식을 세우기 까지 큰 고민 없이 세운것은 처음 인것 같습니다.

 

손으로 적어나가면 문제를 풀어보니 확실히 쉽게 조건을 세울 수 있었습니다.

 

중간에 살짝 고민 했던것은 0의 개수 였는데 기존의 0의 개수를 고려하지 않고 1의 개수로 바꿔주어 틀렸었습니다.

 

다시 노트를 보고 기존의 0의 개수를 고려하지 않았단 것을 깨닫고 코드를 살짝 수정하여 문제를 해결할 수 있었습니다.

반응형