문제 개요
타자가 만들어야 할 총 득점(run)이 주어집니다. 목표는 한 번의 공에서 타자가 1점 또는 2점만 얻어 정확히 그 점수에 도달하는 모든 방법의 수를 구하는 것입니다. 단, 2점이 연속으로 나와서는 안 된다는 제약 조건이 있습니다.
예를 들어 목표 점수가 6이라면 1+2+1+2처럼 도달할 수 있지만, 2+2+1+1처럼 2가 연속되는 방식은 허용되지 않습니다.
예제 1
입력:
score = 4
출력:
연속된 2 없이 1과 2를 사용해 점수에 도달하는 방법의 수: 4
설명: 점수 4에 도달할 수 있는 방법은 다음과 같습니다.
1+1+1+1, 1+1+2, 1+2+1, 2+1+1
예제 2
입력:
score = 5
출력:
연속된 2 없이 1과 2를 사용해 점수에 도달하는 방법의 수: 6
설명: 점수 5에 도달할 수 있는 방법은 다음과 같습니다.
1+1+1+1+1, 2+1+1+1, 1+2+1+1, 1+1+2+1, 1+1+1+2, 2+1+2
접근 방법
이 문제는 재귀 호출을 이용해 해결할 수 있습니다. 핵심 아이디어는 플래그(flag) 변수를 사용해 직전 득점이 2였는지 여부를 기록하는 것입니다. 직전 득점이 2였다면 이번에는 반드시 1을 선택해야 하고, 그렇지 않다면 1 또는 2 중 하나를 자유롭게 선택할 수 있습니다.
- 목표 점수를 저장할 정수형 변수 score를 준비합니다.
- 플래그 변수 check를 false로 초기화합니다. false는 "직전 득점이 2가 아니었다"는 의미입니다.
- 함수 ways_reach_score(int score, bool check)는 남은 점수와 직전 득점 정보를 바탕으로 가능한 방법의 수를 반환합니다.
- 남은 점수가 0이면 유효한 조합 하나를 완성한 것이므로 1을 반환합니다.
- check가 false이고 남은 점수가 1보다 크다면, 다음 두 가지 경우를 모두 고려해 누적합니다.
- 1점을 얻는 경우: ways_reach_score(score − 1, false)
- 2점을 얻는 경우: ways_reach_score(score − 2, true) - check가 true라면 직전 득점이 2였으므로 이번에는 반드시 1점만 얻을 수 있고, ways_reach_score(score − 1, false)만 호출합니다.
- 모든 재귀 호출이 완료되면 count에 총 방법의 수가 누적되며, 이 값을 결과로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int ways_reach_score(int score, bool check){
int count = 0;
if (score == 0){
return 1;
}
if (check == false && score > 1){
count += ways_reach_score(score - 1, false) + ways_reach_score(score - 2, true);
} else {
count += ways_reach_score(score - 1, false);
}
return count;
}
int main(){
int score = 4;
bool check = false;
cout<<"Count of ways to reach a score using 1 and 2 with no consecutive 2s are: "<<ways_reach_score(score, check);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Count of ways to reach a score using 1 and 2 with no consecutive 2s are: 4
성능 개선 팁
위 재귀 풀이는 한 번의 호출마다 최대 두 번의 재귀 호출이 발생하므로, 점수가 커질수록 실행 시간이 지수적으로 증가할 수 있습니다. 이를 개선하려면 메모이제이션(memoization)을 적용해 이미 계산한 (남은 점수, 플래그) 상태의 결과를 배열에 저장하고 재사용하면 됩니다. 이렇게 하면 상태의 수가 유한하므로 전체 시간 복잡도를 선형 수준까지 낮출 수 있어, 큰 입력값에서도 효율적으로 동작합니다.