동적프로그래밍3 [Java][백준] 2775번 부녀회장이 될테야 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 아이디어 ... 1호 2호 3호 4호 5호 ... 5층 1 7 28 74 180 4층 1 6 21 46 106 3층 1 5 15 25 60 2층 1 4 10 20 35 1층 1 3 6 10 15 0층 1 2 3 4 5 문제를 표로 구현해봤다. 예를 들어, 4층의 3호 거주 인원은 4층의 2호 + 3층의 3호 거주 인원과 같다. 따라서 k와 n이 각각 주어졌을 때, k층 n호의 거주 인원을 구하는 공식은 dp[k][n] = dp[k-1][n] + dp[k][n-1] 이다. 1. 0층은 n호에 n명이 거주.. 2024. 2. 5. [Java][백준] 1149번 RGB거리 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 위와 같은 경우는 불가능하며, n번째 집의 색은 n-1번째 집의 색을 제외한 2가지 색 중에서 골라야 한다. 아이디어 1. n번째 집의 색을 선택하려면 n-1번째 집이 어느 색을 선택했는지 저장할 필요가 있다. 따라서 2차원 배열을 사용하기로 했다. 2. 각 집의 RGB 색별 가격을 저장해야 한다. 8 71 39 44 32 83 55 51 37 63 89 29 100 83 58 11 65 13 15 47 25 29 60 66 19 예제를 확.. 2024. 2. 5. [Java][백준] 1463번 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 아이디어1 1. 3으로 나누어 떨어진다면 3으로 나누기 2. 2로 나누어 떨어진다면 2로 나누기 3. 둘 다 해당되지 않으면 -1 수행 우선순위를 이런 로직으로 생각했었는데 반례: 10의 경우 10 -> 5 -> 4 -> 2 -> 1 보다 10 -> 9 -> 3 -> 3이 연산횟수가 더 적기 때문에 아이디어1의 로직이 틀렸다는 것을 알 수 있다. 아이디어2 우선순위를 두지 말고 1, 2, 3번을 각각 수행해서 가장 최소인 연산횟수를 구하자. dp[0] = 0; dp[1] = 0; for (int i=2; i 2024. 2. 5. 이전 1 다음
