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받은 코드 찾아보기 (설명이 꼭 달려있는 코드를 읽자)
그리고 푼 다음에는 반드시 다른 사람의 코드를 봐야 한다.
특히 자신만의 가상의 스승을 잡고 그 분의 코드를 보는 것도 좋은 방법이라 생각한다.
너무 갓갓들은 이상한 방식으로도 짜는 경우도 있기 때문에 적당한 사람을 선택해야 한다.
내가 애용하는 IDE 사이트
(IDE 자동 완성이 불가능하기 때문에 사용하는 중)
문제 :
정수 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;
}
참고한 블로그
'OLD_알고리즘 > Baekjoon' 카테고리의 다른 글
백준] 2446 : 별 찍기 - 9 (0) | 2020.08.12 |
---|---|
백준] 10844 : 쉬운 계단 수 (0) | 2020.08.11 |
백준] 11727 : 2*n 타일링 (2) (0) | 2020.08.10 |
백준] 11726 : 2*n 타일링 (0) | 2020.08.05 |
백준] 1463 : 1로 만들기 (0) | 2020.07.31 |
댓글