다이나믹 프로그래밍

[백준 4095] 최대 정사각형 (C++)

4095번: 최대 정사각형 입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N과 M이 주어진다. (1 ≤ N,M ≤ 1,000) 다음 N개의 줄에는 공백으로 구분된 M개의 수가 주어진다. 마지막 줄에는 0이 두 www.acmicpc.net 반례: 1 1 0 answer : 0 1 2 0 answer : 0 2 1 1 2 answer : 1 dp[r][c] : r,c를 오른쪽 아래 꼭짓점으로 가지는 정방 행렬의 크기. 현재 위치의 왼쪽, 위, 왼쪽 위 대각선의 dp값 중에서 가장 작은 값을 +1 한게 현재 위치의 dp값이 된다. dp[r][c] = min(dp[r-1][c-1], min(dp[r][c-1], dp[r-1][c])) + 1; ❗️주의사항 : answer를 반드시 ..

[백준 1039] 교환 (C++)

1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net N이 100만보다 작다는 조건 덕분에 문제를 해결할 수 있었다. 최대 10번의 교환을 수행할 수 있기 때문에, 몇 번째 교환일 때 어떤 수가 나왔는지 확인한다면 모든 경우의 수를 확인해서 최솟값을 찾을 수 있다. -> check[1000001][11] 처음 숫자가 한자릿수라면 교환이 불가능하기 때문에 -1을 출력한다. 처음 숫자가 두자릿수일 때 일의 자리가 0이라면 교환이 불가능하기 때문에 -1을 출력한다. dp를 수행하면서 교환한 수가 0으로 시작할 때는 넘긴다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1..

[백준 2616] 소형기관차 (C++)

2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 현재 칸을 선택할 때, 선택하지 않을 때를 정해서 재귀를 수행하면 되는 문제이다. 현재 칸을 선택하지 않는다면 현재 칸의 번호를 +1 한 채로 다음 칸으로 넘어간다. 현재 칸을 선택한다면? 현재 칸부터 소형 기관차의 크기만큼 연속된 칸에 타있는 손님의 수를 누적합 배열 parr을 통해서 구해준다. 그리고 현재 칸의 번호를 +소형기관차의크기 한 채로 다음 칸으로 넘어간다. 기저 조건은 소형 기관차를 선택한 횟수가 4가 되거나 현재 칸을 선택해도 소형 기관차의..

[백준 10217] KCM Travel (C++)

10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세 www.acmicpc.net 다익스트라, 다이나믹 프로그래밍 [백준 17182] 우주 탐사선 (C++) 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 hyeo-noo.tistory.com 위 문제와 비슷한 다익스트라+DP문제였다. (주유소_13308 도 비슷하다) 하지만 이번 KCM문제는 최단 시간을 ..

[백준 5527] 전구 장식 (C++)

5527번: 전구 장식 서강대학교의 축제 기간에 상근이는 매년 AS관 복도에 화려한 장식을 꾸민다. 장식은 전구 N개로 이루어져 있고, 전구는 왼쪽에서 오른쪽으로 일렬로 배열되어 있다. 각 전구는 불이 켜있을 수 www.acmicpc.net 다이나믹 프로그래밍 가만히 머리로만 생각할 때는 잘 떠오르지 않다가 손으로 패턴이 될 만한것들을 적다보니까 풀 수 있었다. 가장 긴 증가하는 부분 수열 문제와 비슷한 느낌을 받았다. 증가하는 부분수열의 크기를 구할 때와 비슷하게 연속해서 나타나는 교대 패턴의 최대 길이를 구했다. 1번 예제 : 1 1 0 0 1 0 1 1 1 0 연속해서 나타나는 패턴의 길이는 1 2 4 1 2 이렇게 구할 수 있다. 나뉘는 구간은 그림에 나타난다 나뉘는 구간이 3개가 있다면 두번째 ..

[백준 17182] 우주 탐사선 (C++)

17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 다익스트라, 다이나믹 프로그래밍, 비트마스킹 [백준 13308] 주유소 (C++) 13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리 hyeo-noo.tistory.com 얼마 전 위 문제를 풀면서 다익스트라와 dp를 함께 쓰는 방법에 익숙해진 덕분에 풀 수 있었다 모든 행성이 서로 이..

[백준 13308] 주유소 (C++)

13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도 www.acmicpc.net 다익스트라, 다이나믹 프로그래밍 정점을 지나면서 지금까지 지나온 도시중 리터당 가격이 가장 싼 곳의 가격정보를 들고다니면 된다. 처음에 dist배열을 만들어주지 않고 전체 탐색을 하게해서 메모리초과를 띄웠다. pq에 중복된값이 엄청많이 들어간다고 생각했고 걸러줄 방법이 필요했는데 dp를 사용했다. 현재 정점까지 이동한 비용의 최솟값을 저장하는데 현재 정점에서 가지고 있는 리터당 가격정보도 같이 저장해야한다. dp[현재 정점][리터당 가격의..

[백준 1890] 점프 C++

1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 다이나믹 프로그래밍 dfs top-down방식으로 2차원 cache를 적용한 풀이. Cache[r][c] = r, c에서 점프해서 N-1, N-1에 도달할 수 있는 경우의 수. long long 주의. N-1, N-1에 도달하면 1을 리턴. Map의 원소가 0이면 0을 바로 리턴. 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 ..

[백준 1509] 팰린드롬 분할 C++

1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 다이나믹 프로그래밍 1. 문제 해결 아이디어 일단 문자열의 모든 범위에 따른 팰린드롬 여부를 2차원 table로 만들었다. dp[st][ed]에는 st부터 ed까지의 문자열이 팰린드롬인지 확인여부가 담겨있다. dp table을 채울 때 str[st]와 str[ed]가 같고 dp[st+1][ed-1]이 팰린드롬이면 dp[st][ed]도 팰린드롬인 성질을 이용해서 O(n^2)으로 테이블을 구할 수 ..

[백준 1562] 계단 수 C++

1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 비트필드를 이용한 다이나믹 프로그래밍 1. 문제 해결 아이디어 현재 구한 계단 수의 자릿수, 마지막 숫자 위 2개의 정보를 가지는 2차원 배열로 문제를 해결하려 했었는데 당연히 답이 제대로 나오지 않았다. 0~9의 숫자가 각각 사용되었는지 아닌지 알아야 하기 때문에 (10개의 숫자 각각 사용되었는지 아닌지에 대한 경우의 수 2^10) 따라서 [1