문제 개요
이 문제에서는 세 개의 변수 n, s, k가 주어집니다. 목표는 숫자 n으로 시작하고 길이가 s이며, 인접한 두 요소 사이의 절댓값 차이가 k보다 작은 모든 가능한 시퀀스를 출력하는 것입니다.
주제를 더 잘 이해하기 위해 예시를 살펴보겠습니다.
입력: n = 3, s = 3, k = 2
출력:
3 3 3
3 3 4
3 3 2
3 4 4
3 4 5
3 4 3
3 2 2
3 2 3
3 2 1
위 예시에서 각 시퀀스는 3으로 시작하며 길이는 3입니다. 그리고 인접한 요소 간의 차이는 항상 k(=2)보다 작습니다. 예를 들어 3과 4의 차이는 1, 3과 2의 차이 역시 1로 조건을 만족합니다.
해결 접근 방식
이 문제의 핵심은 인접 요소 간의 절댓값 차이가 k 미만이 되도록 만드는 것입니다. 이를 위해 다음 요소를 현재 값보다 크게 설정해 양수 차이를 얻거나, 작게 설정해 음수 차이를 얻는 방식으로 시퀀스를 구성할 수 있습니다.
구체적인 알고리즘은 다음과 같습니다.
- n부터 시작하여 각 연속 위치에 대해 재귀 호출을 수행합니다.
- 현재 값에 0부터 k-1까지의 값을 더하는 경우를 처리합니다(양의 방향).
- 마찬가지로 현재 값에서 1부터 k-1까지의 값을 빼는 경우도 처리합니다(음의 방향).
- 길이가 s에 도달하면 해당 시퀀스를 출력합니다.
이러한 방식은 재귀(recursion)와 백트래킹(backtracking) 기법을 활용한 전형적인 해결 방법입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void printConsecutiveNumbers(vector<int>& v, int n, int s, int k){
// 길이가 s에 도달하면 시퀀스를 출력
if (s == 0) {
for (int i = 0; i < v.size(); i++)
cout << v[i] << " ";
cout << endl;
return;
}
// 현재 값에 0 ~ k-1을 더하는 경우 (양의 방향)
for (int i = 0; i < k; i++) {
v.push_back(n + i);
printConsecutiveNumbers(v, n + i, s - 1, k);
v.pop_back();
}
// 현재 값에서 1 ~ k-1을 빼는 경우 (음의 방향)
for (int i = 1; i < k; i++) {
v.push_back(n - i);
printConsecutiveNumbers(v, n - i, s - 1, k);
v.pop_back();
}
}
int main(){
int n = 3, s = 3, k = 2;
cout << "The sequence is :\n";
vector<int> v;
v.push_back(n);
printConsecutiveNumbers(v, n, s - 1, k);
return 0;
}
코드 설명
printConsecutiveNumbers 함수는 벡터 v에 지금까지 만들어진 시퀀스를 저장하며 재귀적으로 동작합니다.
- 종료 조건: 남은 길이
s가 0이 되면 벡터에 담긴 시퀀스를 모두 출력하고 함수를 종료합니다. - 양의 방향 탐색: 현재 값
n에 0부터 k-1까지의 값을 더한 수를 다음 요소로 추가한 뒤 재귀 호출합니다. - 음의 방향 탐색: 현재 값에서 1부터 k-1까지의 값을 뺀 수를 다음 요소로 추가한 뒤 재귀 호출합니다.
- 백트래킹: 재귀 호출이 끝나면
v.pop_back()으로 마지막 요소를 제거하여 다른 경우의 수를 계속 탐색할 수 있도록 합니다.
main 함수에서는 초기값 n을 벡터에 먼저 넣고, 나머지 길이(s-1)만큼 재귀 함수를 호출하여 전체 시퀀스를 완성합니다.
실행 결과
The sequence is :
3 3 3
3 3 4
3 3 2
3 4 4
3 4 5
3 4 3
3 2 2
3 2 3
3 2 1
결론
이처럼 재귀와 백트래킹을 활용하면 '첫 요소가 n, 길이가 s, 인접 요소 간 절댓값 차이가 k 미만'이라는 조건을 만족하는 모든 시퀀스를 체계적으로 생성하고 출력할 수 있습니다. 이 기법은 조합을 탐색하는 다른 유사한 문제에도 폭넓게 응용될 수 있습니다.