본문 바로가기

분류 전체보기156

[백준] 2839번: 설탕 배달 (Java) 1. 문제설명상근이는 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕을 담는 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 최대한 적은 봉지를 들고 가려고 한다.시간 제한: 1초메모리 제한: 128MB 2. 접근 방식`dp[i]`를 설탕 무게가 `i`일 때 필요한 최소 봉지 개수를 저장한다.`dp[1] ~ dp[5]` 에 초기값을 설정한다.`i=6` 부터는 `dp[i-3]`과 `dp[i-5]`의 값을 고려하여 계산한다.한 쪽만 0이 아닌 경우: 0이 아닌 값 + 1두 쪽 모두 0이 아닌 경우: `Math.min(dp[i-3], dp[i-5]) + 1`모두 0인 경우: 0으로 설정최종적으로 `dp[n]`이 0이면 -1을 출력, 아니면 dp[n]값을 출력한다. 3. 최종 코드import ja.. 2024. 8. 28.
[백준] 11727번: 2xn 타일링 2 (Java) 1. 문제설명2xn 직사각형을 1x2, 2x1, 2x2 타일로 채우는 방법의 수를 10,007로 나눈 나머지를 구하는 문제이다.시간 제한: 1초메모리 제한: 256MB 2. 접근 방식`dp[i]`에 가로 길이가 i일 때 채우는 방법의 수를 저장한다.`dp[i] = dp[i-1] + dp[i-2] * 2``dp[1]`과 `dp[2]`는 초기값 설정하고, i=3 부터는 점화식을 사용해 값을 구한다. 3. 틀린 이유`dp[i]` 에 값을 저장할 때 점화식 계산한 값을 그대로 넣었더니 데이터 타입을 초과해서 틀렸다.  4. 틀린 부분 수정저장할 때 `% 10007` 연산으로 10007 이하로 값을 저장했다.  5. 최종 코드import java.io.*;public class Main { public st.. 2024. 8. 27.
[백준] 9655번: 돌 게임 (Java) 1. 문제설명돌 게임은 탁자 위에 돌 N개가 있을 때 상근이와 창영이가 턴을 번갈아가면서 돌을 1개 또는 3개 가져가고, 마지막 돌을 가져가는 사람이 이기는 게임이다. 게임은 상근이가 먼저 시작하고, 이기는 사람을 구하는 문제이다.시간 제한: 1초메모리 제한: 128MB 2. 접근 방식REF) https://propercoding.tistory.com/21문제에서 “두 사람이 완벽하게 게임을 했을 때”가 조건이기 때문에 최적의 전략을 사용해야 한다.N=1: 상근이가 돌 1개를 가져가므로 상근이의 승리N=2: 상근이가 1개를 가져가면 창영이가 남은 1개를 가져가므로 창영이의 승리N=3: 상근이가 3개를 가져가므로 상근이의 승리N=4: 상근이가 1개 또는 3개를 가져가면 창영이가 3개 또는 1개를 가져가므로.. 2024. 8. 27.
[백준] 9095번: 1,2,3 더하기 (Java) 1. 문제설명정수 n이 주어졌을 때, n을 1, 2, 3의 조합으로 나타내는 방법의 수를 구하는 문제이다.시간 제한: 1초메모리 제한: 512MB 2. 접근 방식DP 방법을 사용한다.dp[i] 는 i를 1, 2, 3의 합으로 나타낼 수 있는 경우의 수를 저장한다.dp[i] 는 dp[i-1], dp[i-2],dp[i-3] 의 합으로 계산한다. 3. 올바른 접근 방식 및 해결 방식https://lotuslee.tistory.com/43 4. 최종 코드import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(.. 2024. 8. 26.
[백준] 1010번: 다리 놓기 (Java) 1. 문제설명도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강의 흐르고 있다. 다리를 짓기로 하고, 짓기에 적합한 곳(사이트)이 서쪽에 N개, 동쪽에는 M개가 있다.(N≤M) 한 사이트에는 최대 한 개의 다리만 연결될 수 있고, 다리를 최대한 많이 짓기 위해 서쪽의 사이트 개수만큼(N개) 다리를 지으려고 한다.다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 문제이다.시간 제한: 0.5초메모리 제한: 128MB 2. 접근 방식조합의 개념을 사용한다.$_nC_r$ : 서로 다른 n개의 원소에서 r(단, $0$_nC_r = {_{n-1}C_{r-1}} + {_{n- 1}C_{r}}$`int dp[][]` 배열을 사용하여 조합의 값을 저장한다.DP의 Top-Down .. 2024. 8. 26.
[백준] 2748번: 피보나치 수 2 (Java) 1. 문제설명0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 2번째 부터는 다음 점화식을 만족한다.F(n) = F(n-1) + F(n-2)   (n ≥ 2) n이 주어졌을 때, n번째 피보나치 수를 구하는 문제이다. 시간 제한: 1초메모리 제한: 128MB 2. 접근 방식DP - Bottom-Up 방식0, 1번째 피보나치 수를 먼저 계산하고 배열에 저장한다.반복문을 통해 2~n번째 피보나치 수를 순차적으로 계산하고 저장한다.배열의 n번째 값을 반환한다.DP - Top-Down 방식재귀 호출을 통해 n-1, n-2번째 피보나치 수를 계산하고, 두 값을 더해 배열[n]에 저장한다.배열의 n번째 값을 반환한다. 3. 틀린 이유피보나치 수를 저장하는 배열의 타입을 int로 선언했다.예를 들어 n이 .. 2024. 8. 26.
[백준] 1743번: 음식물 피하기 (Java) 1. 문제설명음식물이 통로 중간 중간에 떨어져 있고, 음식물은 근처(상하좌우)에 있는 것끼리 뭉치게 되어 큰 음식물 쓰레기가 된다. 떨어진 음식물 중에 제일 큰 음식물의 크기를 구하는 문제이다.시간 제한: 2초메모리 제한: 128MB 2. 접근 방식음식물 쓰레기가 있는 위치를 load배열에 저장한다. 음식물이 있는 곳을 1로 저장한다.(0, 0) 위치부터 통로를 BFS 탐색한다.큐를 사용해 인접한 상하좌우를 탐색하여 연결된 음식물의 크기를 계산한다.BFS를 통해 구한 음식물의 크기(trashSize)를 maxTrashSize와 비교하여 최댓값을 갱신한다.  3. 최종 코드import java.io.*;import java.util.*;public class Main { static int n, m;.. 2024. 8. 25.
반응형