[JAVA] 백준 2110 - 공유기 설치
2022. 8. 18. 19:24
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 해결 방법 일단 문제를 이해하는 것도 조금 헷갈려서 문제부터 정리해 봄 집 주소로 [1, 2, 4, 8, 9]가 들어오고 공유기 개수가 3개로 들어왔을 때 왜 정답이 3일까? 최대 거리가 1이라면 => [1, 2, 4, 8, 9] 5개의 집에 공유기를 설치해야 됨 최대 거리가 2라면 => 1번집에 공유기를 설치하면 2번집에는 설치하지 않아도..
[JAVA] 백준 11062 - 카드게임
2022. 8. 16. 22:04
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/11062 해결 방법 DP 알고리즘을 사용해서 풀어야 함 먼저 뽑는 근우를 playerA라 하고, 나중에 뽑는 명우를 playerB라고 하고 dp[ i ][ j ] = i ~ j 번째 카드가 남았을 때 playerA의 최대값으로 가정하면 dp[ 1 ][ n ]이 정답이 됨 1장 남았을 때부터 n장 남았을 때까지 거꾸로 생각해보자 dp[ i ][ j ]를 구하려면 dp[ i + 1 ][ j ]와 dp[ i ][ j - 1 ] 값을 알아야 함 ex) 2 4번째 카드가 남았다면 => 3 4번째 카드가 남은 상태에서 2번째 카드를 고른 경우와 2~3번째 카드가 남은 상태에서 4번째 카드를 고른 경우 위 2가지 경우를 고려 dp 배열은 playerA의..
[JAVA] 백준 12920 - 평범한 배낭 2
2022. 8. 16. 18:43
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/12920 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 www.acmicpc.net 해결 방법 평범한 배낭 문제 푸는 방법을 안다고 가정 ( 평범한 배낭 문제 풀이 => https://chb2005.tistory.com/158 ) 평범한 배낭 문제와 유사하지만 물건들의 갯수가 1개 고정이 아닌 최대 10000개 까지 있을 수 있음 따라서 다른 해결책이 필요함 만약 물건1(무게:1, 가치:1)의 개수가 15개라고 가정해보자 처음 생각했..
[JAVA] 백준 12865 - 평범한 배낭
2022. 8. 16. 16:47
JAVA/백준(BOJ) 문제풀이
Knapsack 알고리즘 설명 및 백준 12865 문제 풀이 https://chb2005.tistory.com/158 [JAVA] Knapsack 알고리즘 ● Knapsack 알고리즘 이란? Knapsack은 배낭이란 뜻으로, Knapsack 알고리즘은 배낭 알고리즘 이라고도 불림 Knapsack 알고리즘은 DP의 일종으로 배낭 채우기 문제에서 유래되었음 배낭 채우기 문제란 배 chb2005.tistory.com
[JAVA] 백준 1238 - 파티 ( Reverse Dijkstra )
2022. 8. 16. 14:24
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 해결 방법 n개의 노드가 주어지고 모든 노드에서 노드 X로 갔다 오는 최단 거리를 구해야 함 모든 노드 -> 노드 X + 노드 X -> 모든 노드 와 같이 2부분으로 나누어 생각해 봄 노드 X -> 모든 노드의 최단 경로는 다익스트라 알고리즘을 사용 ( 다익스트라 -> https://chb2005.tistory.com/78 ) 모든 노드 -> 노드 X로 가는 최..
[JAVA] 백준 25307 - 시루의 백화점 구경
2022. 7. 8. 20:51
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/25307 25307번: 시루의 백화점 구경 첫째 줄에 백화점의 세로 길이, 가로 길이, 마네킹과 떨어져야 하는 거리를 의미하는 정수 $N, M, K$가 공백으로 구분되어 주어진다. ($1 \leq N,M \leq 2\,000$, $0 \leq K \leq 4\,000$) 둘째 줄부터 $N$개의 줄 www.acmicpc.net 해결 방법 시루의 시작 위치에서 의자를 찾는 과정은 BFS를 돌리면 될 것이라 생각함 하지만 문제는 마네킹과의 거리가 K 이하인 곳을 방문하지 않아야 된다는 것 만약 모든 마네킹에서 각각 BFS나 DFS 등을 진행하여 갈 수 없는 곳들을 체크한다 마네킹이 최대 2000 * 2000 개 있을 수 있고 K가 최대 4000이..
[JAVA] 백준 25306 - 연속 XOR
2022. 6. 27. 18:26
JAVA/백준(BOJ) 문제풀이
문제 https://www.acmicpc.net/problem/25306 25306번: 연속 XOR 3에서 5까지의 자연수는 3, 4, 5로, 세 개 존재한다. 세 수를 XOR한 값은 (3 XOR 4) XOR 5 = 7 XOR 5 = 2 이다. www.acmicpc.net 해결 방법 문제에서 주어진 A, B의 범위가 10^18으로 매우 큼 하나씩 XOR 연산을 해서 답을 구하면 시간초과 발생할 것임 따라서 시간을 줄일 수 있는 방법을 찾아야 함 XOR 계산은 두 수가 같으면 0, 다르면 1을 뜻함 계산을 몇번 해보다보니 규칙을 하나 발견함 00 xor 01 xor 10 xor 11 의 결과는 항상 0임 그리고 이 앞에 어떤 수가 붙더라도 1이 짝수개 있기 때문에 0일수 밖에 없음 ex) 101110010..