[백준] 2193 - 이친수

문제 링크 : https://www.acmicpc.net/problem/2193

문제 탐색하기

1) 문제 분석

자연수 N (1 ≤ N ≤ 90)이 주어짐
조건을 만족하는 N자리 이친수의 개수를 출력
이친수의 조건
- 0으로 시작하지 않음
- 1이 두 번 연속으로 나타나지 않음

즉, 가능한 이진수들 중에서 위 조건을 만족하는 N자리 수의 개수를 구하는 문제

2) 가능한 시간복잡도

(1) 입력 처리

입력 크기: 단일 정수 N
→ O(1)

(2) DP 테이블 구성

dp[i]: i자리 이친수의 개수
최대 90자리까지이므로 → O(N)

(3) 전체 시간복잡도

입력 처리: O(1)
DP 계산: O(N)
→ 총합: O(N)

3) 알고리즘 선택 이유

이 문제는 피보나치 수열과 같은 점화식을 갖는 문제로, 이전 상태를 기반으로 다음 상태를 계산하는 전형적인 동적 프로그래밍(DP) 문제이다.

dp[n] = dp[n - 1] + dp[n - 2]

이와 같은 점화식이 나온 이유

n자리 이친수는 다음 두 가지 경우로 나뉨
1. 마지막 자리가 0인 경우 → 이전에 0 또는 1이 올 수 있음
2. 마지막 자리가 1인 경우 → 이전은 무조건 0이 와야 함

→ 이 점화식을 통해 불필요한 중복 계산 없이 정답을 구할 수 있음

코드 설계하기

1. 실행 구조

1) 입력 처리

입력값: N (자리 수)

2) DP 테이블 초기화

dp[1] = 1
dp[2] = 1 (단, 입력이 2 이상일 때만 할당)

3) 점화식 기반 DP 계산

dp[i] = dp[i - 1] + dp[i - 2]
3부터 N까지 반복

4) 정답 출력

console.log(dp[N])

2. 고민이 되었던 부분

1) 입력 처리에서의 에러 대응

: dp[2]를 무조건 할당할 경우, 입력이 1일 때 존재하지 않는 배열 접근이 발생할 수 있음

→ if (N >= 2) 조건으로 안전하게 처리

2) 2차원 DP 대신 1차원 DP 선택

dp[i][0], dp[i][1] 등 이차원 배열도 가능하지만,
단순히 개수만을 세면 되기 때문에 1차원 배열로 충분함

→ 점화식 기반으로 더 간결하고 오류 가능성이 적음

정답 코드

JavaScript

// 사용 언어 : Javascript

const fs = require('fs');
const input = fs.readFileSync(0, 'utf-8').trim();
const N = Number(input);

const dp = new Array(N + 1).fill(0);
dp[1] = 1;
if (N >= 2) dp[2] = 1;

for (let i = 3; i <= N; i++) {
  dp[i] = dp[i - 1] + dp[i - 2];
}

console.log(dp[N]);

마무리하며

어제 개인적인 일정으로 인해 문제를 못 풀었기에, 오늘은 꼭 문제를 풀어야겠다며 초심의 마음을 다시 가졌다. 이번 문제는 단순한 수열 문제처럼 보이지만, “이진수의 성질”과 “DP 점화식 유도”가 정확히 연결되어야 하는 문제였다.

특히 초기값 설정, 불필요한 계산 제거, 입력 예외 처리 등 작지만 중요한 디테일을 신경 쓰지 않으면 ‘틀렸습니다’가 발생할 수 있기에, 단순 구현보다는 “문제 조건을 수학적으로 해석해 점화식을 세우는 능력”이 요구됐다고 느꼈다 .앞으로도 문제를 풀 때 단순히 구현만 하지 않고, 조건의 수학적 구조와 해법을 논리적으로 정리하는 습관을 유지하고 싶다.

최근 글