9095 1,2,3 더하기 +

1,2,3 더하기 (9095)

 

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 9095 1, 2, 3 더하기

int T, n;

int solve(int sum){
	// 기저 사례 : 지금까지 더한 합이 n 과 같으면 종료
	if(sum == n){
		return 1;
	}
	else if(sum > n){
		return 0;
	}
	
	int ret = 0;
	
	// 첫 번째 자리부터 n 번째 자리까지 재귀를 돈다.
	for(int j = 1; j <= 3; j++){
			ret += solve(sum + j);
	}
	
	return ret;
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> T;
	
	while(T--){
		cin >> n;
		cout << solve(0) << '\n';
	}
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

1. 비슷한 문제를 풀어본 적이 있던가?

  형태가 비슷하거나 관련 문제를 풀어보았다면, 같은 방법을 사용할 거라고 예측할 수 있다. 그러나, 완전히 같은 문제를 만날 가능성은 없기에 문제의 목적을 보고 적절한 접근 방법을 선택할  수 있어야 한다. 이를 위해, 해당 문제가 어떤 문제인지 분류하는 힘을 익히고 우리가 익히는 알고리즘들이 어느 경우에 사용될 수 있는지 체계적으로 알아가야 한다.

2. 단순한 방법에서 시작할 수 없을까?

 이 책에서 많은 연습문제는 "무식하게 풀 수 있을까" 라는 질문으로 풀이가 시작된다. 시·공간의 제약을 생각하지 않고 가장 단순한 알고리즘을 만들어 보는 것이다. 이는 간단하게 풀 수 있는 문제를 너무 복잡하게 생각해서 어렵게 푸는 실수를 방지해준다. 

 효율적인 알고리즘이라도 단순한 알고리즘을 기반으로 구성된 경우가 많기 때문에, 단순한 알고리즘을 구현해두고 여기에서 좀 더 효율적인 자료 구조를 사용하거나, 최적화를 하는 등의 점진적인 개선을 통해 효율적인 알고리즘을 구현해낼 수 있다.

풀이

1. 최대 경우의 수를 구해보자.

- 1 을 n 개 더해서 만드는 것이 최대 개수일 것이다. 각 자리당 1,2,3 3개의 수가 들어갈 수 있으므로 최대 개수는 3^n

n 이 10 이하 이므로 3^10 이 최대이다. 1억보다 훨씬 작으므로 브루트 포스를 시행해볼 수 있다.

2. 자리를 옮길 때마다 바뀌는 것은 무엇일까.

- 지금까지의 합

- 위치

지금까지의 합만이 중요하므로, 지금까지의 합을 함수의 파라미터로 설정한다. (초기에 구상을 그렇게만 하는 것이지 문제를 푸는 와중에 파라미터를 추가하거나 제거할 수 있다. 필요한 파라미터를 먼저 생각해보는 접근 방식은 도움이 많이 되었었다.)

3. 함수의 구현 방향을 재귀로 잡고, 어떻게 구현할 것인지 정한다.

- 각 칸에 1,2,3 을 모두 넣어보는 것이다. 그렇게 재귀를 이어나가다가 합이 n 과 같으면 1개의 경우라는 의미로 1을 return 한다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

- 이전에 풀었던 이 문제  코드를 보면 점화식을 찾아내어 문제를 풀어내었다. 물론 이 방법이 시간 복잡도가 더 낮다. 로직 자체가 가지는 효율성은 저러한 접근 방식이 유리하지만, 문제를 풀어내는 입장에서는 브루트 포스가 가능하다는 것을 알고 아무 생각없이 컴퓨터에게 문제 풀이를 맡기는 것이 더 유리할 수 있다는 것을 깨달았다.

- 최대 경우의 수를 구해보는 것. 문제의 전체적인 흐름을 좌지우지 할 수 있다.