DP

[2163] 초콜릿 자르기

https://www.acmicpc.net/problem/2163 2163번: 초콜릿 자르기 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 www.acmicpc.net 💡 내 코드(C++) // [2163] 초콜릿 자르기 /*초콜릿을 결국 1x1크기로 다 쪼갠다면 경우의 수는 한가지 밖에 없는데 왜 ..

[2133] 타일 채우기

https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 예제 입력 1 복사 2 예제 출력 1 복사 3 힌트 아래 그림은 3×12 벽을 타일로 채운 예시이다.... www.acmicpc.net 💡 내 코드(C++) /*[2133] 타일 채우기*/ /*https://www.acmicpc.net/problem/2133*/ #include using namespace std; int main(void) { int n, sum = 0; int dp[31]; cin >> n; dp[0] = 0, dp[2..

[1912] 연속합

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 💡 내 코드(C++) /*[1912] 연속합*/ /*https://www.acmicpc.net/problem/1912 */ #include #include using namespace std; int main(void) { int n, max; int arr[100001], dp[100001]; cin >> n; for (int i = 0; i > arr[i]; } dp[0] ..

[1904] 01타일

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수 www.acmicpc.net 💡 내 코드(C) #include int main(void) { int n; long dp[1000001] = { 0 }; dp[0] =..

[1699] 제곱수의 합

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 www.acmicpc.net 💡 내 코드(C++) /*[1699] 제곱수의 합*/ /*https://www.acmicpc.net/problem/1699 */ /*d..

[1463] 1로 만들기

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 🔎 해결 방법 ucpc 캠프 2일차 '다이다믹 프로그래밍' 에서 제일 처음으로 풀었던 문제. 캠프 때 풀지 못해서 집에와서 다시 도전해보았는데 틀렸습니다 계속 떠서 접을 뻔...ㅎ 내가 실수한 부분 c에서는 기본적으로 min, max함수를 제공하지 않기 때문에 반드시 매크로를 정의해주어야 한다. (예를 들어, #define min(a, b) (((a) > n; dp[0] = 0, dp[1] = 0; for(int i = 2 ; i