Puyo Puyo #11559
문제 이해
- 높이 12, 너비 6의 그리드
- 셀은 '.' (빈공간), 또는 색깔 'R', 'G', 'B', 'P', 'Y'로 주어진다
- 같은 색의 셀이 4개 이상 상하좌우 연결되면 빈공간이 된다
- 한 차례에서 4개 이상 연결된 동일 색상 셀이 모두 처리되면 색상이 있는 모든 셀을 모두 수직 아래로 떨어뜨린다.
- 몇 차례를 거치는지 출력한다
해결방안
단순한 시뮬레이션 문제라 판단했다.
매 차례(문제에서는 연쇄라 일컫는다)를 play() 메서드로 처리한다. 이 메서드 내에서는 다음과 같은 처리를 수행한다
- 빈 공간이 아닌 모든 셀에 대해 동일 색상으로 4개 이상 연결되어 있는지 확인하고, 처리하는 작업을 수행한다 => (i, j)에 대해
pangpang메서드를 수행한다 - 모든 셀에 중력을 가한다 =>
gravity - 빈 공간으로 대체된 셀이 있는지 여부를 리턴한다 => 있을 경우 계속 플레이
static boolean play() {
boolean success = false;
for (int i =0; i < H; i++) {
for (int j = 0; j < W; j++) {
boolean[][] visited = new boolean[H][W];
if (grid[i][j] != '.') {
if (pangpang(i, j, visited)) {
success = true;
}
}
}
}
gravity();
return success;
}1. 4개 이상 상하좌우로 연결된 동일 색상의 셀이 있는지 확인하고, 있으면 '.'로 대체한다
static boolean pangpang(int startY, int startX, boolean[][] visited) {
char color = grid[startY][startX];
ArrayDeque<int[]> sameColor = new ArrayDeque<>();
List<int[]> result = new ArrayList<>();
sameColor.add(new int[] {startY, startX});
visited[startY][startX] = true;
result.add(new int[]{startY, startX});
while (!sameColor.isEmpty()) {
int[] node = sameColor.pollFirst();
int y = node[0];
int x = node[1];
for (int d = 0; d < 4; d++) {
int ny = DY[d] + y;
int nx = DX[d] + x;
if (isValidCoordinate(ny, nx) && !visited[ny][nx] && color == grid[ny][nx]) {
visited[ny][nx] = true;
result.add(new int[] {ny, nx});
sameColor.add(new int[] {ny, nx});
}
}
}
if (result.size() >= 4) {
for (int[] coordinate : result) {
int y = coordinate[0];
int x = coordinate[1];
grid[y][x] = '.';
}
return true;
}
return false;
}2. 모든 셀에 중력을 가한다
'.'이 아닌 모든 셀들을 덱에 순차적으로 더한 다음, 덱의 마지막 요소부터, 컬럼의 맨 아래 칸부터 채워간다.
static void gravity() {
char[][] newGrid = new char[H][W];
newGrid = initializeGrid(newGrid);
for (int col = 0; col < W; col++) {
ArrayDeque<Character> chars= new ArrayDeque<>();
for (int row = 0; row < H; row++) {
if (grid[row][col] != '.') {
chars.add(grid[row][col]);
}
}
int row = H-1;
while (!chars.isEmpty()) {
newGrid[row--][col] = chars.pollLast();
}
}
grid = newGrid;
}3. 이번 차례에서 빈 공간으로 대체된 셀이 있으면 다음 차례를 진행한다. 없으면 끝
int count = 0;
while (play()) {
count++;
}
output.append(count);풀이 코드
사이클 게임 #20040
문제 이해
- 점 n개와 게임 횟수 m번이 주어진다
- 3 <= n <= 500,000
- 3 <= m <= 1,000,000
- 점 n개는 0부터 n-1까지 고유한 번호를 갖는다
- 일직선에 놓인 점은 없다
- 매 차례에 점 a와 b를 잇고자 한다
- 사이클이 발생하면 몇번째 차례에서 발생했는지 출력한다
- 모든 차례가 끝날 때까지 사이클이 발생하지 않으면 0 을 출력한다.
해결방안
cycle을 보고 Prim 알고리즘을 떠올렸다. Prim 알고리즘은 a 와 b가 같은 집합에 속하는지 확인한 다음 union하기 때문에 사이클 발생 여부를 확인하기 편리하다.
union-find 코드
static void make() {
parents= new int[n];
size = new int[n];
Arrays.fill(parents, -1);
Arrays.fill(size, 1);
}
static int findSet(int a) {
if (parents[a] < 0) return a;
return parents[a] = findSet(parents[a]);
}
static boolean union(int a, int b){
int aRoot = findSet(a);
int bRoot = findSet(b);
if (aRoot == bRoot) return false;
if (size[bRoot] > size[aRoot]) {
size[bRoot] += size[aRoot];
parents[aRoot] = bRoot;
} else {
size[aRoot] += size[bRoot];
parents[bRoot] = aRoot;
}
return true;
}Prim + 사이클 없으면 0 출력
int count = 1;
make();
int[][] edges = new int[m][2];
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
edges[i][0] = v1;
edges[i][1] = v2;
}
for (int[] edge : edges) {
if (!union(edge[0], edge[1])) break;
count++;
}
sb.append(count == m+1 ? 0 : count);풀이 코드
오답노트
일단 정석대로 코드를 완성한 다음 꼼수를 부리자
동전 #9084
문제 이해
- 테스트케이스 T개가 주어진다 (1이상 10이하)
- 각 테스트케이스마다
- 동전의 가짓수 N개 (1<=N<=20)
- 각 동전의 금액이 오름차순으로 주어진다
- 목표 금액 M이 주어진다 (1<=M<=10000)
해결방안
'경우의 수'를 보는 순간 DP 접근이 필요하다는 생각이 들었다.
- 모든 동전에 대해 금액 0 을 만들 수 있는 가짓수는 1이다. 즉, 동전을 사용하지 않는 것.
dp[i][0] = 1; - 가장 작은 동전 금액으로 0부터 M까지의 금액을 만들 수 있는 가짓수를 저장한다.
- i번째 동전에 대해 dp를 하기 전에, i-1번째 행의 값을 모두 복사한다
- i번째 동전에 대해 j 금액을 만들 수 있는 가짓수를 확인한다.
2. i번째 동전에 대해 j 금액을 만들 수 있는 가짓수를 확인한다.
금액 j에서 현재 동전 금액 m을 뺀 값(j-m)이 동전들에 의해 만들어질 수 있는 값이라면 (dp[i][j-m] > 0), j-m을 만들 수 있는 가짓수를 현재 dp[i][j]에 더한다.
풀이 코드
import java.util.*;
import java.io.*;
public class Main {
static int N, coins[], M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
int T = Integer.parseInt(st.nextToken());
for (int t = 1; t <= T; t++) {
N = Integer.parseInt(br.readLine());
coins = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
coins[i] = Integer.parseInt(st.nextToken());
}
M = Integer.parseInt(br.readLine());
int[][] dp = new int[N][M+1];
for (int i = 0; i < N; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= M; i++) {
if (i % coins[0] == 0) dp[0][i] = 1;
}
for (int coinIdx = 1; coinIdx < N; coinIdx++) {
for (int totalMoney = 0; totalMoney <= M; totalMoney++) {
dp[coinIdx][totalMoney] = dp[coinIdx-1][totalMoney];
if (totalMoney - coins[coinIdx] >= 0 && dp[coinIdx][totalMoney - coins[coinIdx]] > 0) {
dp[coinIdx][totalMoney] += dp[coinIdx][totalMoney - coins[coinIdx]];
}
}
}
sb.append(dp[N-1][M]).append("\n");
}
bw.write(sb.toString());
bw.flush();
br.close();
bw.close();
}
}오답노트
솔직히 DP는 아직도 모르겠다. 골드 수준 DP는 거의 처음 풀어본 것 같은데 가장 어려웠다. 감도 안온다. 이걸 어쩌냐 ㅋㅋㅋㅋ큐ㅠㅠㅠㅠ
시험 감독 #13458
문제 이해
문제 설명이 직관적이라 스킵한다
해결방안
일단 총감독관은 꼭 1명 있어야 한다. 부감독은 0명 이상 존재한다.
long sum = 0;
for (int i = 0; i < N; i++) {
sum += 1;
if (takers[i] - B > 0) sum += (long) Math.ceil((double)(takers[i] - B)/(double)C);
}풀이 코드
오답노트
마이너스 값에 대해 나눗셈하면 마이너스 값이 나온다.ㅋㅋㅋ
아기 상어 #16236
문제 이해
- N x N 그리드가 주어진다
- 2 <= N <= 20
- 각 셀은 빈 공간, 물고기, 또는 상어다
- 0: 빈칸
- 1, 2, 3, 4, 5, 6: 칸의 물고기 크기 의미
- 9: 상어
- 상어
- 시작 크기: 2
- 이동:
- 자신보다 큰 물고기가 있는 칸: 지나갈 수 없음. 먹을 수 없음
- 자신과 같은 크기의 물고기: 지나갈 수 있음. 먹을 수 없음
- 자신보다 작은 크기의 물고기: 지나갈 수 있음. 먹을 수 있음
- 자신의 크기와 같은 수의 물고기를 먹으면 크기 1 증가
- 섭취
- 가장 가까운 물고기부터 먹음 (사방탐색 이동, 한 칸 당 1초 소요)
- 같은 거리면 행 작은 순, 그 다음 열 작은 순으로 먹음
- 상어가 더 이상 먹을 물고기가 없으면 엄마에 도움을 요청한다
- 상어가 몇 초 동안 엄마에게 도움을 요청하지 않고 잘 먹고 다니는지 출력
해결방안
단순한 시뮬레이션 문제다.
- 상어 위치에서 BFS로 가장 가까운 물고기 찾음
- 없으면 시간 출력, 있으면 먹고 1 반복
1. 상어 클래스 정의
static class Shark {
int size, fishEaten, y, x;
Shark(int y, int x) {
this.y = y;
this.x = x;
this.size = 2;
this.fishEaten = 0;
}
}2. 물고기 클래스 정의
static class Fish {
int y, x, distance;
Fish(int y, int x, int distance) {
this.y = y;
this.x = x;
this.distance = distance;
}
}3. 현재 상어 위치의 기준으로 BFS를 수행한다
int[][] visited배열에 셀까지의 최단 경로를 저장한다- 섭취 가능한 최단 경로의 셀을 찾았으면 같은 경로 길이의 섭취 가능한 셀을 모두 모은다
- BFS가 끝나면 섭취가능한 최단 경로 셀들을 행 작은순, 그 다음 열 작은 순으로 정렬하여 다음으로 섭취할 물고기를 리턴한다
- 먹을 수 있는 물고기가 없으면 -1의 물고기를 리턴한다.
static Fish bfs() {
ArrayDeque<int[]> queue = new ArrayDeque<>();
int[][] visited = new int[N][N];
queue.add(new int[] {babyShark.y, babyShark.x});
visited[babyShark.y][babyShark.x] = 1;
int minDist = Integer.MAX_VALUE;
List<int[]> ans = new ArrayList<>();
while (!queue.isEmpty()) {
int[] node = queue.pollFirst();
int y = node[0];
int x = node[1];
if (visited[y][x] > minDist) break;
if (isConsumable(y, x)) {
minDist = Math.min(minDist, visited[y][x]);
if (visited[y][x]==minDist) ans.add(new int[]{y, x});
}
for (int d = 0; d < 4; d++) {
int ny = y + DY[d];
int nx = x + DX[d];
if (isValidCoordinate(ny, nx) && visited[ny][nx] == 0 && grid[ny][nx] <= babyShark.size) {
visited[ny][nx] = visited[y][x] + 1;
queue.add(new int[] {ny, nx});
}
}
}
if (ans.isEmpty()) return new Fish(-1, -1, -1);
else {
Collections.sort(ans, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
return Integer.compare(a[1], b[1]);
}
});
return new Fish(ans.get(0)[0], ans.get(0)[1], minDist-1);
}
}4. BFS가 -1을 리턴하면 더 이상 먹을 수 있는 물고기가 없으니 종료한다.
static void simulate() {
Fish nextFish = bfs();
if (nextFish.y==-1) return;
time += nextFish.distance;
grid[nextFish.y][nextFish.x] = 0;
babyShark.fishEaten++;
babyShark.y = nextFish.y;
babyShark.x = nextFish.x;
if (babyShark.fishEaten == babyShark.size) {
babyShark.size++;
babyShark.fishEaten=0;
}
simulate();
}풀이 코드
오답노트
시뮬레이션 문제는 언제나 문제를 잘 읽어야 한다
청소년 상어 #19236
문제 이해
- 4 x 4 그리드에 1부터 16의 번호를 매긴 물고기가 존재한다
- 각 물고기는 1부터 8까지의 방향을 갖는다
- 상어는 (0,0)에 등장하며 해당 셀의 물고기를 섭취하고 그 물고기의 방향을 얻는다
- 이제 상어가 더 이상 물고기를 먹을 수 없을 때까지 물고기 이동과 상어 이동을 반복한다.
- 상어가 먹은 물고기 고유번호의 최대합을 구한다
물고기의 이동
- 물고기의 고유 번호 오름차순으로 이동한다
- 현재 방향에서부터 45도씩 왼쪽으로 회전하며 한 칸 전진할 수 있는지 확인한다
- 상어가 있는 칸에는 전진하지 못한다
- 물고기가 있는 칸이면 스왑한다
- 빈공간이면 전진한다
상어의 이동
- 방향을 바꿀 수 없다
- 대신 거리는 자유자재다 => 모든 경우의 수를 확인해야 한다
- 물고기가 없는 칸에는 이동할 수 없다
- 물고기를 섭취하면 그 물고기의 고유번호만큼 점수를 얻고, 그 물고기의 방향을 얻는다
- 상어가 먹은 물고기는 사라진다
해결방안
또 시뮬레이션 문제다
int[][] grid에 물고기의 인덱스를 담아 (i,j) 좌표에 위치하는 물고기의 인덱스를 알 수 있게끔 한다.
이 인덱스로 Fish[] school를 접근하면 물고기의 정보를 알 수 있다.
1. 상어 클래스를 정의한다
static class Shark {
int y, x, direction;
Shark(int y, int x, int direction) {
this.y = y;
this.x =x;
this.direction =direction;
}
}2. 물고기 클래스를 정의하고, 물고기 배열에 담는다
static class Fish {
int y, x, idx, direction;
Fish(int idx, int direction, int y, int x) {
this.idx = idx;
this.direction = direction;
this.y = y;
this.x = x;
}
}물고기는 항상 16마리로 정의되어 있고, 1부터 16의 고유번호를 갖기 때문에 Fish[] school = new Fish[16 + 1]에 담을 수 있다.
static class Fish {
int y, x, idx, direction;
Fish(int idx, int direction, int y, int x) {
this.idx = idx;
this.direction = direction;
this.y = y;
this.x = x;
}
}3. 시뮬레이션을 시작한다
3-1. 그리드에 상어가 (0,0)에 등장하며, 해당 물고기를 먹고, 그 고유번호만큼의 점수와 방향을 얻는다
static void simulate(int[][] grid, Fish[] school) {
Shark shark = new Shark(0, 0, school[grid[0][0]].direction);
int initialFish = grid[0][0];
school[grid[0][0]] = null;
grid[0][0] = 0;
moveFish(grid, school, shark);
moveShark(initialFish, grid, school, shark);
}3-2. 물고기의 이동과 상어의 이동을 반복한다. 상어의 이동은 다양한 케이스를 모두 탐색해야 하기 때문에 DFS를 수행한다
물고기의 이동
static void moveFish(int[][] grid, Fish[] school, Shark shark) {
for (int i = 1; i <= 16; i++) {
if (school[i] == null) continue;
Fish fish = school[i];
for (int d = 0; d < 8; d++) {
int nextDirection = nextDir(fish.direction, d);
int ny = fish.y + DY[nextDirection];
int nx = fish.x + DX[nextDirection];
if (isValidCoordinate(ny, nx) && !sharkIsHere(ny, nx, shark)) {
int tmp = grid[ny][nx];
grid[ny][nx] = fish.idx;
grid[fish.y][fish.x] = tmp;
if (tmp != 0) {
school[tmp].y = fish.y;
school[tmp].x = fish.x;
}
school[i].direction = nextDirection;
school[i].y = ny;
school[i].x = nx;
break;
}
}
}
}상어의 이동 (DFS)
static void moveShark(int fishEaten, int[][] grid, Fish[] school, Shark shark) {
totalFish = Math.max(fishEaten, totalFish);
for (int dist = 1; dist <= 4; dist++) {
int ny = shark.y + dist*DY[shark.direction];
int nx = shark.x + dist*DX[shark.direction];
if (isValidCoordinate(ny, nx) && grid[ny][nx] > 0) {
Fish eatenFish = school[grid[ny][nx]];
Shark newShark = new Shark(ny, nx, eatenFish.direction);
int[][] newGrid = duplicateGrid(grid);
Fish[] newSchool = duplicateSchool(school);
newGrid[ny][nx] = 0;
newSchool[eatenFish.idx] = null;
moveFish(newGrid, newSchool, newShark);
moveShark(fishEaten + grid[ny][nx], newGrid, newSchool, newShark);
}
}
}풀이 코드
우당탕탕