문제 개요
이 문제에서는 하나의 정수 n이 주어지며, n부터 시작해 값이 0 또는 음수에 도달할 때까지 감소한 뒤, 다시 원래의 n까지 증가하는 수열 패턴을 출력하는 것이 목표입니다.
예를 들어 문제를 이해해 보겠습니다.
입력: n = 12
출력: 12 7 2 -3 2 7 12
접근 방법
for나 while 같은 반복문을 사용하지 않고 재귀(recursion)를 활용해 이 문제를 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 현재 값이 양수(m > 0)인 동안에는 값을 출력하고, 5를 뺀 값으로 재귀 호출을 이어갑니다.
- 재귀 호출이 끝나고 되돌아오는 시점에 현재 값을 한 번 더 출력하면, 감소 구간과 증가 구간이 자연스럽게 모두 완성됩니다.
즉, 재귀의 "호출" 단계에서는 감소하는 부분을, "복귀" 단계에서는 증가하는 부분을 처리하게 됩니다.
구현 예제
아래 코드는 위 접근 방식의 실제 구현입니다.
#include <iostream>
using namespace std;
void printNextValue(int m){
if (m > 0){
cout<<m<<'\t'; // 감소 구간 출력
printNextValue(m - 5); // 5씩 줄이며 재귀 호출
}
cout<<m<<'\t'; // 복귀 시 증가 구간 출력
}
int main(){
int n = 13;
cout<<"The pattern is:\n";
printNextValue(n);
return 0;
}
실행 결과
The pattern is −
13 8 3 -2 3 8 13
동작 원리와 복잡도
n = 13일 때 함수의 실행 흐름을 살펴보면, 먼저 13 → 8 → 3 → -2 순서로 재귀 호출이 깊어지며 감소 구간이 출력됩니다. m = -2가 되면 조건(m > 0)이 거짓이 되어 더 이상 재귀 호출이 일어나지 않고, 이후 각 호출이 종료되면서 되돌아가는 길에 -2 → 3 → 8 → 13이 차례로 출력되어 증가 구간이 완성됩니다.
- 시간 복잡도: O(n / 5) — 값이 5씩 감소하므로 약 n/5번의 호출이 발생합니다.
- 공간 복잡도: O(n / 5) — 재귀 호출 스택이 같은 깊이만큼 쌓입니다.
이처럼 재귀 함수의 호출과 복귀 단계를 활용하면, 반복문 없이도 감소 후 증가하는 대칭형 패턴을 간결하고 우아하게 출력할 수 있습니다.