기맹기 개발 블로그

BOJ 17404 RGB거리 2 난이도 : 골드 4 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 전략 전형적인 DP 문제이다. i 번째 집을 j 색으로 칠하는 비용을 cost[i][j]라고 하자. 0번째 집 ~ i 번째 집을 칠할 때 i번째 집을 j 색으로 칠했을 때 최소 비용을 다음과 같은 점화식으로 표현할 수 있다. dp[i][j] = cost[i][j] + min( {dp[i - 1][j가 아닌 색] } )..

BOJ 16946 벽 부수고 이동하기 4 난이도 : 골드 2 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 전략 N, M blankCount[r][c] 2. 1인 칸에 대해서 상하좌우 blankCount를 더한다. 시행착오 4 5 11001 00111 01010 10101 위의 예시를 보자. 1의 과정이 끝난 다음에 blankCount는 다음과 같이 기록될 것이다. 00220 33000 30101 01010 이 때 map..

BOJ 17143 낚시왕 난이도 : 골드 1 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 전략 구현문제이지만 시간초과가 나지 않도록 해야한다. R, C c) { shark.dir = opposite(shark.dir); ny = shark.y + dy[shark.dir]; nx = shark.x + dx[shark.dir]; } shark.y = ny; shark.x = nx; } } 상어의 위치 갱신을 O(1)만에 할 ..

BOJ 26157 즉흥 여행 (Hard) 난이도 : 플래 3 https://www.acmicpc.net/problem/26157 26157번: 즉흥 여행 (Hard) 첫째 줄에 나라의 개수 $ N $과 항공편의 개수 $ M $이 주어진다. $( 1 \le N \le 200\,000; $ $ 0 \le M \le 500\,000 )$ 둘째 줄부터 $ M $개의 줄에 걸쳐 항공편의 정보가 두 정수 $ v $ $ w $로 주어진다. 이는 $ v $ www.acmicpc.net 전략 SCC에 속한 임의의 두 정점은 방문할 수 있다. 위의 예시에서는 그래프 전체가 하나의 SCC이므로 모든 정점이 결과가 된다. 위의 예시에서는 SCC는 [1], [2, 3, 4] 두 개이며 SCC로 그래프를 압축하면 [1] -> [..

BOJ 2150 Strongly Connected Component 난이도 : 플래 5 https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 전략 SCC를 공부하면서 종만북의 타잔 알고리즘으로 구현해보았다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; ..

BOJ 2473 세 용액 난이도 : 골드 3 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 전략 생각할 수 있는 가장 간단한 방법은 세 용액의 모든 조합을 찾는 것이다. 3중 for문으로 세 용액의 조합을 만든다면 O(N^3)이다. N의 범위는 [3, 5000] 이므로 N^3은 5^3 * 10억이다. 따라서 다른 방법을 찾아야 한다. 만약 두 개의 용액 조합을 찾는다면 나머지 하나의 용액은 모두 찾을 필요 없이 이진 탐색..

BOJ 12100 2028 (Easy) 난이도 : 골드 2 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 전략 각 라운드마다 위 / 아래 / 왼쪽 / 오른쪽 4방향으로 이동시킬 수 있다. 문제에서 최대 5번으로 제한을 뒀으므로 모든 경우의 수는 4^5 = 1024이다. 브루트포스로 가능하기 때문에 구현에 초점을 둬서 진행한다. 시행착오 셀 충돌하고 병합하는 과정을 구현하면서 루프의 범위가 잘못된 경우가 있었다. 이..

BOJ 2623 음악프로그램 난이도 : 골드 3 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 전략 위상정렬을 사용하여 풀 수 있는 문제임을 알 수 있다. 2252 줄세우기 문제와 비슷하지만 다른 점이 있다. 예제의 입력을 보면 이렇게 각 PD별로 가수의 순서를 정할 수 있는데, 1:1이 아니라 여러명의 가수의 순서를 정하는 것이다. 이로 인해 하나의 노드에서 여러 개의 링크를 가질 수 있다. 따라서 링크를 배열로 저장하여..