::SemiColon;;

1. 문제 https://www.acmicpc.net/problem/1654 2. 풀이 이 문제는 답을 이분탐색을 이용하여 구하는 문제이다. 답은 1부터 2^31 - 1사이에 존재한다. 따라서 이 사이의 값 중 답이 되는 값중에 최댓값을 구하기 위해 이분탐색을 사용하면 된다. 또 다른 주의할점은 이분탐색을 할때 mid값을 구할때 m = (l + r) / 2인데 l이 1이고, r이 2^31 - 1이어서 더하게 되면 int형 사이즈를 초과하기때문에 l, r, m을 long long 형으로 변환시켜줘야한다. 3. 소스코드 #include #include using namespace std; int n, k, arr[10000]; bool makeN(int m) { int line = 0; for (int i ..

1. 문제 https://www.acmicpc.net/problem/2579 2. 풀이 이 문제는 DP를 이용해 푸는문제이다. dp[i]는 i번째 계단은 밟고, 1부터 i번째까지 최대의 수이다. 즉 dp[i]는 그 바로 전단계의 계단을 밟은 여부에 따라 바뀌는 것이다. (시작) dp[0] = 0 dp[1] = arr[1] dp[2] = arr[1] +arr[2] (3≤i≤n) dp[i] = max(dp[i-2] + arr[i], dp[i-3] + arr[i-1] +arr[i])이다. cf) https://zcacoding.tistory.com/20 [백준/BOJ] 2156 - 포도주 시식 (c++) (DP) 1. 문제 https://www.acmicpc.net/problem/2156 2. 풀이 이 문제는..

1. 문제 https://www.acmicpc.net/problem/1932 2. 풀이 이 문제는 DP를 이용하여 푸는 문제이다. 이번 dp배열은 2차원 배열을 사용할 것이다. 점화식부터 살펴보자면 초기값: dp[0][0] = tri[0][0] (j=0) dp[i][j] = dp[i-1][j] + tri[i][j] (j=i-1) dp[i][j] = dp[i-1][j-1] + tri[i][j] (1≤j≤i-2) dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + tri[i][j] 이다. dp는 위에서부터 최대값을 구할 것이다. 자기자신의 위에 있는 왼쪽, 오른쪽 중 dp값의 더 큰 값을 구해 자기자신(tri[i][j])의 값과 더하면 dp[i][j]가 만들어지는 것이다. 하지만 맨..

1. 문제 https://www.acmicpc.net/problem/9461 2. 풀이 문제에서 P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 이라고 하였다. 위의 수열을 보면 P(i) = P(i-2) + P(i-3)이라는 것을 알 수 있다. 이를 통해 코딩을 하면된다. 3. 소스코드 #include using namespace std; int t, n, mxn = 3; long long dp[101]; int main() { ios::sync_with_stdio(0); cin.tie(), cout.tie(); dp[1] = dp[2] = dp[3] = 1; cin >> t; while (t--) { cin >> n; if (mxn < n) { for (..

1. 문제 https://www.acmicpc.net/problem/2156 2. 풀이 이 문제는 DP를 이용하여 푸는 문제이다. 중요한점은 dp[i]를 i번째 포도주(자기자신)을 먹은 여부에 따라 설정하는 것이다. 일단 첫번째로 i번째 포도주(자기자신)을 먹었다고 한다면 i번째 포도주(자기자신)을 먹었기 때문에 i-1번째 포도주를 안 먹었다면 dp[i] = dp[i-2] + arr[i]이다. i-1번째 포도주를 먹었다면 dp[i] = dp[i-3] + arr[i-1] + arr[i]이다. 두번째로 i번째 포도주(자기자신)를 안먹었다고한다면 i-1번째 포도주를 먹든 안먹든 상관이 없어지기 때문에 dp[i]는 dp[i-1]이게 된다. 즉 dp[0] = 0, dp[1] = arr[1], dp[2] = dp[..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 위의 문제는 계단수의 성질와 DP를 이용하여 푸는 문제입니다. 맨 앞자리는 0이 오지못한다는 주의할 점도 있습니다. 맨뒷자리에 따라 뒤에 올 수 있는 수가 정해져있습니다. 맨 뒷자리가 0: 1, 1: 0, 2, 2: 1, 3, ... 8: 7, 9, 9: 8 이렇게 됩니다. 즉 인접하는 수의 전단계 계단수를 더하면 현재의 계단수를 구할 수 있게되는것입니다. 점화식으로 작성해보자면 dp[i][j]: 길이가 i이고 마지막 수가 j인 계단수의 개수 j=0 이면 dp[i][0] = dp[i-1][1] j=9 이면 dp..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이번문제는 dp(다이나믹 프로그래밍)를 이용하여 푸는 문제이다. 예시들을 쭉 세워보면 n = 1은 0, n = 2는 1, n = 3은 1, n = 4는 2, n = 5는 3, n = 6은 2 이다. 위의 예시들 중 n = 6을 보면 6은 3으로도 나누어 떨어지고, 2로도 나누어 떨어진다. 따라서 6을 3으로 나눈값, 2로 나눈값, 1을 뺸값을 다 비교해보아야한다. 즉 dp[6] = min(dp[6/3], dp[6/2], dp[6-1])이다. 이를 토대로 점화식을 세워보면 dp[i] = min(dp[i/3] (i..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 이 문제의 푸는 방법을 먼저 말하자면 피보나치 배열과 똑같은 답이다. 이유는 n = 1일때 아래와 그림과 같이 2×1 하나로 되어 결과는 1이다. n = 2일때는 아래와 그림과 같이 2×1 2개, 1×2 2개로 조합하여 만들 수 있기에 결과는 2이다. n = 3일때는 두가지 경우로 나눌 수 있는데 왼쪽의 그림은 n = 2의 그림에 단지 2×1 1개만 붙인 것이다. 왼쪽의 그림은 n = 1의 그림에 단지 1×2 2개만 ..

https://www.acmicpc.net/problem/1003 피보나치 함수는 대표적인 다이나믹프로그래밍 문제이다. 피보나치 함수는 f(0) = 0, f(1) = 1, n>=2, f(n) = f(n-1) + f(n-2)의 꼴이다. 위의 문제는 0이 나오는 횟수와 1이 나오는 횟수를 출력하는 것이다. 따라서 n=0: {1,0} n=1: {0,1} n=2: {1,1} n=3: {1,2} n=4: {2,3} .... 이렇게 이어진다. 위의 순서를 보고 규칙을 찾으면 n=i: {i-1 의 첫번째 원소 + i-2 의 첫번째 원소, i-1 의 두번째 원소 + i-2 의 두번째 원소}이다. 따라서 이에 맞게 함수를 작성하면 pair fibo(int a) { if (dp[a] != make_pair(0, 0)) r..

https://www.acmicpc.net/problem/1149 기본적인 DP문제입니다. 문제를 푸는 아이디어는 집을 색칠할 수 있는 3가지 색깔의 경우의수를 모두다 구해보는 것입니다. 코드로는 for (int i = 1; i < N; i++) { dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + input[i][0]; dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + input[i][1]; dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + input[i][2]; } 이렇게 될것입니다. dp[i][j]는 i번째 집을 j색깔로 칠했을때의 최소비용입니다. 따라서 dp[i][0]은 i번째 집을 0번 페인트로 칠했을때 ..