종이와 펜을 들고, 써보자.
규칙을 찾고, 적절한 전략을 선택해 구현하자.
생각을 하면서 퍼뜩 이 알고리즘 전략을 사용해야겠군~!이라는 깨달음을 얻겠다는 마인드로 풀어보자.
문제
https://www.acmicpc.net/problem/1904
문제분석
N=1일 때부터 찬찬히 생각해보자
N = 1일 때는 0,또는 1
N = 2일 때는 00,01,10,11 이어야하지만, 문제의 조건으로 인해 00,11만 가능하다.
N = 3일 때는 000, 001 , 010, 011, 100, 101, 110, 111 을 만들 수 있어야했지만, 문제의 조건으로 인해 001, 100, 111 만 가능하다.
이전 수행의 결과는 다음 수행과 연관되어 있나?
그렇다. 이전 수행의 결과에 1또는 00카드를 추가하여 새로운 수를 만들 수 있다. 그런데 문제는 00카드를 추가하면 길이가 +2가 된다는 것이 문제이다.
그래서 현재 수행을 기준으로 이전 수행들을 살펴보았다.
N이 3인 경우는 N=1일 때와, N=2일 때가 영향을 준다. N=1일 때 00을 더함으로써, N=2일 때의 결과들에 1 카드를 추가함으로써 길이가 3이되기 때문이다.
그러므로, N=3의 결과는 N=1과 N=2에 의해 영향을 받는 셈이다.
그러면 카드를 앞뒤로 붙여봐야하나?
아니다. 그렇게 되면 수가 겹치는 경우가 생긴다.
가령, N=1의 1카드의 앞에 00을 붙이면 001이 되는데,
이 결과는 N=2일 때의 00에 1 카드를 뒤에 붙인 것과 동일하다.
이 실험으로 우리는 새로운 카드는 무조건 뒤에만 붙인다를 깨닫게 되었다.
발견한 규칙
N 길이의 카드를 만드는 조건은 N-1길이의 카드를 만드는 경우의 수 + N-2길이의 카드를 만드는 경우의 수이다.
선택한 알고리즘 전략
이제 값을 출력해보자.
- 재귀
- DP
두 가지 방법으로 구현이 가능하다.
재귀는 너무 시간이 오래걸릴 것 같다.
DP로 시간을 단축시키자. 이제 구현은 당신의 몫이다.
잡생각
유형탐색의 중요성
코딩 테스트는 제한시간 내에 빠르게 문제의 핵심을 파악해서 올바른 답을 적어내냐를 판가름하는 시험이다. 만약 내가 모르는 문제가 있다면, 그것은 내가 아직 유형 탐색이 제대로 되어있지 않았기 때문이다.
내가 코딩테스트를 처음 공부할 때는 이걸 대체 어떻게 풀어?라는 생각 밖에 안들었다. 하지만 비슷한 유형의 문제들을 풀수록 문제에서 요구하는 개념을 더 빠르게 찾아내고 구현할 수 있게 되었다.
훈련이 잘 되어 있어야 한다
어느 정도 공부를 하고 보니 취업을 위한 코딩 테스트는 마치 범위가 어느 정도 정해져 있는 수학시험이라는 생각이 들었다. 이 시험을 잘 보기 위해서는 훈련이 잘 되어있어야 한다. 그러기 위해선 꾸준하게 연습해야 한다. 결국 꾸준함이다.
성공한 풀이
const N = require('fs').readFileSync(0).toString().trim() * 1
const dp = new Array(N + 1).fill(0)
dp[1] = 1
dp[2] = 2
for (let i = 3; i < N + 1; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % 15746
}
console.log(dp[N])
Wow