백준] 9095 : 1, 2, 3 더하기

BOJ에서 다음 문제들을 쭉 순서대로 풀어본다.  boj.kr/문제번호 <= 형태로 검색하면 된다.

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

 

 

1시간 넘어가면 풀던 짓을 그만두고 반드시 AC받은 코드 찾아보기 (설명이 꼭 달려있는 코드를 읽자)

그리고 푼 다음에는 반드시 다른 사람의 코드를 봐야 한다.

특히 자신만의 가상의 스승을 잡고 그 분의 코드를 보는 것도 좋은 방법이라 생각한다.

너무 갓갓들은 이상한 방식으로도 짜는 경우도 있기 때문에 적당한 사람을 선택해야 한다.

 

알고리즘 문제풀이(PS) 시작하기

 

내가 애용하는 IDE 사이트

(IDE 자동 완성이 불가능하기 때문에 사용하는 중)

Ideone.com

---

 

9095번: 1, 2, 3 더하기

 

문제  :

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

 

입력  : 

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

 

 

출력  : 

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

 

 

 

 

접근 방법

n = 4
1 + 3 -> 1의 경우의 수에 3을 더한다
2 + 2 -> 2의 경우의 수에 2를 더한다
3 + 1 -> 3의 경우의 수에 1을 더한다

이 때 1~3의 합으로만 나타낼 것이기 때문에 뒤에 더해지는 것만 고려하면 된다.

따라서 점화식은
dp[ n ] = dp[n - 1] + dp[n - 2] + dp[n - 3];
으로 세울 수 있다.

또한 한 번에 식을 세웠기 때문에 i값이 1부터 시작되었을 때
dp[i - 2] + dp[i - 3]이 음수가 나오기 때문에
int i = 4부터 시작해주고,
dp[1]~dp[3]을 구해서 직접 배열에 초기화한 후에 시작한다.

간단한 문제이기 때문에 이렇게 할 수 있는 것이라 생각이 든다.

좀 더 어렵게 낸다면 충분히 어려워질 수 있는 문제일 것이다.


이 문제는 꼭 다시 풀어봐야겠다.

[ 스스로 생각해봄 (생각한 시간 : 1시간 5분) ]

 

일단 처음 문제를 이해하는 것부터 오래걸렸다.ㅎ

한국 사람이지만 한글은 언제나 어렵당...

 

거두절미하고, 일단 의식의 흐름대로 어떻게 문제를 풀어나가야 할 지 적어보려고 한다.

 

이 문제에서는 1, 2, 3의 합으로 나타내는 방법을 구하는 프로그램을 작성해야 한다.

 

문제의 예에서 정수 4가 주어졌을 때는

방법의 수는 총 7가지이다.

 

점화식은 arr[n] = arr[n-1] + arr[n -2] * 2 + arr[n-3] * 3;

n = 4

arr[0] = 1;

arr[1] = arr[0] + arr[1] * 2 + arr[2] * 3;

arr[2] = arr[1] + arr[0] * 2 + arr[1] * 3; 

arr[3] = arr[2] + arr[2] * 2 + arr[0] * 3;

 

아악...

아니면 애초에 int arr[n]={1,}; 로 초기화를 한 후에

각 배열 요소를 2가 되게 또는 3이 되도록 더한 후에 총 합이 n이 되는 지를 구해야 하낭...

 

점화식이 안 떠오른다...

 

 

다시 처음으로 돌아가서 dp로 문제를 푸는 방법은

dp[ ] 에 이전 계산 결과를 저장해놓고 재사용하는 방식이다.

 

아니 머리로는 알겠는데...

활용하는 게 왜 안 되냐고요... 답답하다ㅠㅠㅠ

 

아하

양수이며 11보다 작은 n은 어쨋든 모두 1로 더할 수 있는 방법이 있다.

따라서 dp[1] = 1부터 놓고 시작해도 될 것 같다.

 

그러면 합이 된다는 의미가... 정수 n을 1, 2, 3으로 나눌 수 있다는 의미라..고 생각이 든다.

dp[i] = dp[i - 1] + n / i..?

 

--------

 

점화식은 arr[n] = arr[n-1] + arr[n -2] * 2 + arr[n-3] * 3;

=>
내가 생각했던 점화식에서.. 곱하기만 빼면 된당ㅎ

왜 곱하기를 넣었냐면,

이전에 블록 구할 때처럼

n - 2일 때는 +1+1 & +2가 가능하기 때문에

n - 2일 때, 두 가지의 경우가 가능하다고 생각했다.

 

 

 

정답 코드

#include <iostream>
using namespace std;

int main() {

	int n, T;
	int dp[11];
	
	cin >> T;

	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;
	
	for(int i = 0; i < T; i ++){
		cin >> n;	
	
		for(int j = 4; j <= n; j++){
			dp[j] = dp[j - 1] + dp[j - 2] + dp[j - 3];
		}
		cout << dp[n] << endl;
	}

	return 0;
}

 

 

 

 

 

참고한 블로그

백준 9095번 : 1, 2, 3 더하기