본문 바로가기

알고리즘 문제/백준81

[백준] 17396번: 백도어 (Java) 1. 문제설명0번째에서 N-1번째 분기점까지 가는 최단 거리를 구하는 문제이다. 이때 적의 시야에 걸리는 곳은 지나칠 수 없다. 시야 정보가 0이면 상대 시야에 보이지 않고, 1이면 상대 시야에 보인다. 시야에 걸리지 않으면서 N-1번째 분기점에 도달하는 최단 거리를 구한다.시간 제한: 2초메모리 제한: 512MB 2. 접근 방식`Node` 객체를 사용하여 각 노드(`end`)에 그 노드의 비용(`time`)을 저장하고, 우선순위 큐에서 경로 비용이 짧은 순서대로 처리된다.각 분기점 사이의 정보를 `List[] list` 에 저장한다. (인접리스트 방식, 양방향으로 저장)다익스트라 알고리즘을 사용하여 최단 거리를 구한다.우선순위 큐를 사용하여 가장 짧은 경로를 먼저 처리하고, 현재 경로에서 더 짧은 경로.. 2024. 9. 10.
[백준] 11726번: 2xn 타일링 (Java) 1. 문제설명2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 10,007로 나눈 나머지를 구하는 문제이다.시간 제한: 1초메모리 제한: 256MB 2. 접근 방식`dp[i]`는 `i` 길이의 직사각형을 채우는 방법의 수를 저장한다.`dp[1]`과 `dp[2]`의 초기값을 설정한다.위 그림을 참고하면 `dp[i] = dp[i-1] + dp[i-2]` 점화식을 구할 수 있다.`dp[i]`를 저장할 때 오버플로우 방지를 위해 문제에서 주어지는 10,007로 나눈 값을 저장한다.최종적으로 `dp[n]`을 구한다. 3. 최종 코드import java.io.*;public class Main { public static void main(String[] args) throws IOExcep.. 2024. 8. 29.
[백준] 가장 긴 짝수 연속한 부분 수열 (small) (Java) 1. 문제설명길이가 N인 수열 S가 있고, S는 1 이상인 정수로 이루어져 있다. 수열 S에서 원하는 위치에 있는 수를 골라 최대 K번 삭제할 수 있다. 삭제를 수행 후 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구하는 문제이다.시간 제한: 1초메모리 제한: 1024MB 2. 접근 방식`dp[i][j]`: 수열의 `i` 번째까지의 원소에서 `j` 개의 홀수를 제거했을 때의 가장 긴 짝수 부분 수열의 길이만약 `s[i]`가 짝수일 경우 이전 상태에서 `j` 개의 홀수를 제거한 것과 동일한 상태에서 현재 짝수를 추가하여 길이를 1 증가시킨다⇒ `dp[i][j] = dp[i-1][j] + 1`만약 `s[i]`가 홀수이고,현재 홀수를 제거 가능할 경우 (j > 0) 이전 상태에서 `j-.. 2024. 8. 28.
[백준] 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.
반응형