반응형 백준58 백준 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. 백준 1654. 랜선 자르기 🅰 백준 1654. 랜선 자르기 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net ✏️ 문제 풀이 나무자르기와 마찬가지로 이분탐색을 이용하여 정답이 되는 값을 도출해내는 문제이다. start값을 1로 설정해주는게 중요하다. 또한 end값을 N개의 랜선 중 최고 길이의 값, mid = (start+end)/2 로 설정해주었다. 재귀함수의 기저조건으로 start>end 이면 결과값을 출력해주었고 for문안에서 각 랜선 / mid를 정수형으로 변환하여 cnt에 더해주었다. height값과.. 2021. 9. 7. 백준 2805. 나무자르기 🅰 백준 2805. 나무자르기 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net ✏️ 문제 풀이 이분탐색을 이용하여 정답이 되는 값을 도출해내는 문제이다. start값을 0, end값을 N개의 나무중 최고 높이의 값, mid = (start+end)/2 로 설정해주었다. 재귀함수의 기저조건으로 start>end 이면 결과값을 출력해주었고 for문안에서 각 나무들과 mid의 차이가 0보다 크면 상근이가 가져갈 수 있는 height 값에 더해주었다. height값과 M을 비교.. 2021. 9. 7. 백준 1992. 쿼드트리 🅰 백준 1992. 쿼드트리 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net ✏️ 문제 풀이 영상이 4개로 압축되어 진행되므로 4개의 시작점을 구해서 재귀를 돌려주었다. 또한 출력을 맞춰주기 위해 재귀가 시작되기 전에 "("를 출력해주고, 재귀가 끝나면 ")"를 출력해주었다. ✏️ 소스코드 import java.util.*; import java.io.*; public class Main { static int N; static int tree[][]; public static void main(.. 2021. 9. 6. 이전 1 2 3 4 5 ··· 7 다음
