겜돌이의 개발일지

문제 백준 13398 연속합 2 C++ 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 점화식을 이용하여 문제를 해결합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include #include using namespace std; int arr[100000]; int dp[100000][2]; int main() { ios::sync_with_stdio(false); cin.tie(0)..

문제 백준 5582 공통 부분 문자열 C++ 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 풀이 예제 입력을 보겠습니다. A B R A C A D A B R A E C 1 A 1 1 1 1 1 D 1 A 1 1 1 1 1 D 1 A 1 1 1 1 1 B 1 1 R 1 1 B 1 1 C 1 R 1 1 D 1 A 1 1 1 1 1 R 1 1 A 1 1 1 1 1 s1를 문자열 1의 길이, s2를 문자열 2의 길이라고 하면 dp[0][0] 부터 dp[s2-1][s1-1] 까지 루프를 돌면서 s1과 s2..

문제 백준 9084 C++ 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 풀이 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include #include #include using namespace std; int dp[10001]; int main() { int t; cin >> t; while (t > 0) { // 입력 int n; cin >> n;..

문제 백준 2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 풀이 먼저 LIS (최장 증가 부분 수열)을 구합니다. LIS에 해당하지 않은 원소를 옮겨주면 되므로 n-LIS가 답이 됩니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include #include using namespace std; int dp[201]; int main() {..

문제 백준 11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 풀이 nCr = n * (n -1) * (n-2) * ... * (n-r+1) / r! 이지만 n과 r이 커지면 오버플로우가 발생합니다. 따라서 파스칼의 법칙을 사용하여 dp로 해결합니다. 위 그림을 보면 nCr에서 r이 0이거나, n = r일 때는 1, 나머지 경우에는 nCr = n-1Cr-1 + n-1Cr 입니다. 1C0과 1C1의 초기값을 설정해주고 dp를 이용해 nCk을 구합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..

문제 백준 11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 풀이 [i, j]에서 [i+1, j], [i][j+1], [i+1][j+1]로 이동할 수 있습니다. [i+1][j+1]은 어차피 [i+1, j], [i][j+1]를 거쳐 이동할 수 있으므로 고려하지 않아도 됩니다. (돌아서 갈 때 얻는 사탕이 무조건 크거나 같습니다.) 따라서 dp[i]j[j]에는 dp[i-1][j], dp[i][j-1] 중 더 큰 값에 map[i][j]를 더해준 값을 넣습니다. 소스 코드 1 2 3 4 5 6 ..

문제 백준 1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 해당 영역에서 가장 큰 길이를 계산해 담고 있는 dp 배열을 이용합니다. 먼저 0열과 0행에는 입력값과 똑같은 값을 넣어줍니다. 0열과 0행을 제외하고, 해당 칸의 입력이 0이라면, 어짜피 사각형의 길이는 0이 되므로 dp에 0을 넣어줍니다. 1이라면 왼쪽, 위쪽, 왼쪽 위 3가지 값을 탐색하면서 dp 값을 구합니다. dp값과 최대 길이 값을 비교하여 최댓값을 갱신합니다. 예제를 보겠습니다. square 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 dp 0 1 0 0 0 1 0 0 0 0 0행과..

문제 백준 2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 dp 배열은 (인덱스, 몇번 연속으로 마셨는지) 중에서 최댓값을 나타냅니다. 예제로 보겠습니다. 6 10 13 9 8 1 0 0 6 16 23 28 33 1 6 10 19 25 31 29 2 0 16 23 28 33 32 먼저 1번째, 6일 때 안 마시는 경우(dp[0][0])를 0, 2번 연속 마시는 경우는 없으니 0으로 초기화 해줍니다. 1번 연속 마시는 경우에는 arr[0]값인 6을 넣어줍니다. 2번째에서 안 마시는 경우는 dp[i-..

문제 백준 9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 점화식만 알면 쉽게 풀 수 있는 문제입니다. 점화식은 직관...으로 찾았습니다. 인덱스가 커지면 배열의 값이 int 범위를 초과하므로 배열을 long long 형으로 선언합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include using namespace std; long long dp[101]; int main() { int t; int n..

문제 백준 9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 점화식을 이용합니다. i 번째에서 더해줄 수 있는 방법의 가지수는 3가지입니다. 1더하기, 2더하기, 3더하기 i 번째 오는 방법을 i+1, i+2, i+3에 각각 더해줍니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include using namespace std; int dp[14]; int main() { int t; cin >> t; dp[0] = 1; for (int i = 0; i n; cout