본문 바로가기
반응형

백준/DP9

백준 5557. 1학년 🅰 백준 5557. 1학년 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net ✏️ 문제 풀이 2차원 배열을 이용해서 각 수식을 순서대로 +, - 해서 dp[][] index에 저장한다. 행은 각 수식의 수만큼 만들고 계산되는 수식은 0~20 사이에 있기 때문에 열은 0~20으로 생성한다. dp[N+1][21] 계산해서 나오는 값들은 index로 표현할 수 있기 때문에 각 숫자마다 +연산을 한 값이 20보다 작거나 같으면 dp[i][j+number[i]] += dp[i-1][j], -연산을 한 값이 0보다.. 2021. 9. 27.
백준 1495. 기타리스트 🅰 백준 1495. 기타리스트 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net ✏️ 문제 풀이 기타리스트 문제에서는 행을 각 곡의 개수, 열을 0~M(최대 볼륨)으로 설정한 다음 dp를 수행한다 점화식은 D[i][j] = D[i+1][j+V[i+1]] = 1, D[i+1][j-V[i+1]] = 1이 될 수 있다. i+1에 데이터를 저장할 때 0~M사이에 있으면 dp에 저장을 하면서 마지막 곡까지 반복수행한다. 마지막 곡의 볼륨조절이 끝난 후 그 행에 있는 볼륨 중 최대값을.. 2021. 9. 27.
백준 12920. 평범한 배낭 2 🅰 백준 12920. 평범한 배낭 2 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 www.acmicpc.net ✏️ 문제 풀이 평범한 배낭문제와 비슷하지만 다른점은 "한 물건을 두개 이상 챙기는 것도 가능하다." 이 부분이다. 처음 이 부분을 해결하기 위해 물건이 2개이상 있는 경우에는 for문을 이용하여 2개,3개,4개...k개 만큼을 넣었을 때의 가치를 비교하여 최적의 가치를 찾아서 제출했다 하지만 6%때 시간초과가 떠서 최악의 경우를 생각해보니 가방의 무게가 10,000이고 100개의 물품.. 2021. 9. 27.
백준 12865. 평범한 배낭 🅰 백준 12865. 평범한 배낭 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net ✏️ 문제 풀이 먼저 버틸수 있는 무게 K만큼 반복하면서 현재의 물건이 가방에 넣을 수 있는지 확인해서 dp를 수행한다. product배열에 물품들의 무게, 가치를 저장해주고 dp배열은 N+1,kg+1로 생성해준다 2중 for문을 사용하면서 바깥 for문에는 물품의 수만큼 반복하고, 안쪽 for문에는 넣을수 있는 무게만큼(kg) 반복해준다 예제 입력 데이터 4 7 .. 2021. 9. 26.
백준 2294. 동전 2 🅰 백준 2294. 동전 2 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net ✏️ 문제 풀이 coin배열에 사용할 수 있는 동전을 전부 저장한다. 이중for문을 이용해서 바깥쪽 for문에는 coin의 개수만큼 반복하고, 안쪽 for문에는 가치의 합인 k만큼 반복을 한다 점화식 : if(j-coin[i] >= 0 && D[j-coin[i]!=max_value) : D[j] = min(D[j], 1 + D[j - coin[i]]) 만약 j를 현재 coin[i]로 계산할 수 있고, 이.. 2021. 9. 26.
백준 11066 파일합치기 https://kyunstudio.tistory.com/75 [C++] 백준 11066 - 파일 합치기(동적 계획법, 이후에 다시 보자) 0. 주어진 문제 파일 합치기 성공 한국어 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 256 MB 7555 3967 2521 51.862% 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데 kyunstudio.tistory.com https://developerbee.tistory.com/97 [알고리즘 / 백준] 11066 - 파일 합치기 www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한.. 2021. 9. 26.
백준 1890. 점프 🅰 백준 1890. 점프 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net ✏️ 문제 풀이 dp에 현재 경로값을 저장해서 나감 배열 전체를 탐색하는 것이 아니라서 시간이 오래 안걸림 이중for문을 통해 배열을 반복하면서 이동할 수 있는지 확인 한 후, 이동 가능하면 check배열에 갈수있는 경로에 현재 check의 개수를 더해준다 배열을 확인 다 하면 마지막 지점이 정답이 된다. ✏️ 소스코드 package dp; import java.io.*; import java.util.*; public cla.. 2021. 9. 23.
백준 11048. 이동하기 🅰 백준 11048. 이동하기 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net ✏️ 문제 풀이 dp로 생각해보면 한 좌표에서 올 수 있는 값은 위, 왼쪽, 왼쪽 위 대각선 3가지 이다. 가져올 수 있는 사탕의 최대값을 구해야 하기 때문에 이전 3가지 값 중 최적의 값을 가져오면 된다. 하지만 첫째줄 행, 첫째줄 열은 대각선탐색, 위, 왼쪽 탐색등에 제약이 있으므로 basevalue로 값을 넣어주고 나머지 행에 대해서 이전 값 중 최적값을 구해서 마지막 map[N][M]이 정답이 된다. ✏️ 소스코.. 2021. 9. 23.
백준 2293. 동전 1 🅰 백준 2293. 동전 1 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net ✏️ 문제 풀이 0.5초의 시간제한과, 4MB의 메모리 제한이 있기 때문에 1차원 배열로 풀었다. 예제를 이용해서 설명을 하면 || 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 1 dp[] = 1 1 1 1 1 1 1 1 1 1 2 0 1 1 2 2 3 3 4 4 5 dp[] = 1 2 2 3 3 4 4 5 5 6 5 0 0 0 0 1 2 2 3 3 4 dp[] = 1 2 2 3 4 6 6 8 8 10 동전.. 2021. 9. 22.

티스토리툴바