본문 바로가기

분류 전체보기177

[백준] 1463번: 1로 만들기 (Java) 1. 문제설명정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위의 연산 세 개를 적절히 사용해서 1을 만들려고 한다.연산을 사용하는 횟수의 최솟값을 구하는 문제이다.시간 제한: 0.15초메모리 제한: 128MB 2. 접근 방식`dp[i]`에 i를 1로 만드는데 필요한 소 연산 횟수를 저장한다.점화식을 계산한다.`dp[2]`, `dp[3]`은 각각 1로 초기화 한다.`dp[i]`는 기본적으로 `dp[i-1] +1`로 초기화 한다. (1을 빼는 연산)i가 2의 배수이면, `dp[i]`는 `dp[i/2] + 1`과 비교하여 더 작은 값을 선택한다.i가 3의 배수이면, `dp[i.. 2024. 8. 28.
[백준] 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.
반응형