BOJ (34) 썸네일형 리스트형 BOJ 11057 오르막 수 https://www.acmicpc.net/problem/11057 - DP - 3중 for문 - 예외처리 : 길이가 1일 때 #include int d[1005][11]; int mod = 10007; int main(){ int n; scanf("%d", &n); // 길이가 1인 경우 처리 for(int i=0; i BOJ 10844 쉬운 계단 수 https://www.acmicpc.net/problem/10844 - DP - d[] : 길이가 n인 계단 수 - 예외처리 할 것이 늘어남! : 길이가 1일때 : 길이 2이상일 때 - 모든 0과 9에 대하여 #include int d[102][10]; long long int mod = 1000000000; long long ans=0; int main(){ int n; scanf("%d", &n); for(int i=1; i BOJ 2193 이친수 https://www.acmicpc.net/problem/2193 - DP - DP는 쪼갠다! - 수의 범위를 보고 자료형을 잘 선택하자! : 피보나치의 46항 이상이 되면 int로 표현할 수 없다. #include long long int d[95]; int main(){ int n; scanf("%d", &n); d[0]=0; d[1]=1; for(int i=2; i BOJ 11052 카드 구매하기 https://www.acmicpc.net/problem/11052 - DP - 입력으로 주어진 가격을 저장하는 배열 a[] - d[] : 구해야 할 것 - 이중 for문을 이용해야 해서 헷갈렸다. : d[i]를 구할때마다 1~i까지 중 최댓값을 계속 비교해야한다 #include #include using namespace std; int a[1010]; //주어진 것 int d[1010]; //구할 것 int main(){ int n; scanf("%d", &n); for(int i=1; i BOJ 9095 1,2,3 더하기 https://www.acmicpc.net/problem/9095 - 역시 DP 문제 - 점화식만 찾으면 거의 풀었다고 볼 수 있는데 점화식 찾기가 어렵다.. - 이 문제에서는 테스트 케이스 갯수가 주어지기 때문에 d[]를 모두 구하고 필요한 것만 출력하였다. #include int d[12]; int main(){ int cnt,n; scanf("%d", &cnt); d[0]=1; d[1]=1; d[2]=2; for(int i=3; i BOJ 11727 2×n 타일링 2 https://www.acmicpc.net/problem/11727 - 11726번을 풀었다면 바로 풀 수 있는 문제 - 풀면서도 스스로 놀람.. 점화식을 잘 세우자! #include int d[1005]; int main(){ int n; scanf("%d", &n); d[0]=1; d[1]=1; for(int i=2; i BOJ 11726 2×n 타일링 https://www.acmicpc.net/problem/11726 - DP - 문제 자체는 상당히 어렵게 느껴졌는데 막상 풀고나니 그리 어려운 문제는 아니었음 : 이런것이 DP구나 - 최종 출력은 10007로 나눈 나머지를 나타내야 하는데 for문 바깥에서 출력할 때 %계산을 했는데 틀렸다. : overflow - 계산할 때 마다 나눠줘야 함. for문 안에서 d[]에 넣을 때 %계산하니 통과. #include int d[1005]; int main(){ int n; scanf("%d", &n); d[0]=1; d[1]=1; for(int i=2; i BOJ 1463 1로 만들기 https://www.acmicpc.net/problem/1463 - DP를 이용해서 푼 첫번째 문제. - 점화식을 세우는 것이 중요하다! - DP에서는 [ 재귀 또는 for문 ] 을 이용하여 문제 solve 가능 당연히 for문 이용한 것이 시간복잡도 적게 걸린다. #include int d[1000010]; int main(){ int n; scanf("%d", &n); d[1]=0; for(int i=2; id[i/2]+1){ d[i]=d[i/2]+1; } if(i%3==0 && d[i]>d[i/3]+1){ d[i]=d[i/3]+1; } } printf("%d", d[n]); return 0; } 이전 1 2 3 4 5 다음