두부의 코딩일기

https://www.acmicpc.net/problem/2116 2116번: 주사위 쌓기 첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 www.acmicpc.net 풀이 주사위 면은 총 6개, 주사위 개수는 최대 10,000개이므로 완전 탐색으로 진행해도 시간제한에 지장이 없다. 주사위 면을 A, B, C 대신 인덱스로 표현하면 아래와 같다. 위 문제의 조건은 아래층 주사위의 윗면과 위층 주사위의 아랫면의 숫자가 같아야한다. 가장 바닥에 올 수 있는 면은 6개의 면 중에서 한 개이므로 1-6까지 반복문을 돌리면서 찾아주면 된다. 아랫면이 정해지면 주사위 맞은 편인..

https://www.acmicpc.net/problem/2564 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net 풀이 동근이의 위치와 각 상점 사이의 최단 거리의 합을 구하면 된다. 해당 문제에서 동근이가 상점으로 갈 수 있는 경로는 시계 방향, 반시계 방향 2가지가 존재한다. 동서남북으로 이루어진 직사각형 모양의 맵을 일직선으로 가정하고 풀면 쉽게 해결할 수 있다. 좌측 상단(0, 0) 부터 시작해서 시계방향으로 이어서 일직선으로 생각해준다. 일직선으로 가정했다면 최단 거리를 계산할 때 쉬워질 수 있다. 동근이..

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 풀이 어린 시절에 많이 풀었던 스도쿠가 보이길래 한 번 풀어봤다. 문제의 조건은 우리가 알고 있는 스도쿠와 동일하다. 각 행과 열에 중복되지않은 9개의 숫자(1-9)가 존재해야 한다. 3x3 크기의 박스에 중복되지않은 9개의 숫자(1-9)가 존재해야 한다. 스도쿠에서는 위 두 가지 조건만 신경써주면서 빈칸에 1-9를 넣어주는 dfs를 돌려주면 된다. 하지만 dfs만 계속 돌리면 시간 초과가 ..

https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 풀이 위 문제의 로직은 아래와 같다. 낚시왕이 한 칸 오른쪽으로 이동한다. 해당 열에 해당하는 가장 가까운 상어를 잡는다. 살아있는 상어들은 이동한다. 1. 낚시왕이 한 칸 오른쪽으로 이동한다. for (int i=1; i

https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 풀이 가장 많은 고층 건물이 보이는 건물을 구하고, 거기서 보이는 건물의 수를 출력하라. 고층 건물이 보이기 위해선 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야한다. A와 B를 이은 선분의 기울기를 따져보면 쉽게 문제를 해결할 수 있다. 사실 필자도 기울기를 어떻게 구하는건지 몰라서 검색해봤다. 건물 A와 건물 B를 이은 선분의 기울기를 구하기 위해선 두 건물..

https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 풀이 4 x 4 크기의 공간에 물고기 16마리가 존재한다. 상어가 먹을 수 있는 물고기 번호의 최댓값은? 위 문제의 로직은 아래와 같다. 상어가 물고기를 잡아먹는다. 물고기가 이동한다. 1-1. 맨 처음 상어는 (0, 0)에 있는 물고기를 잡아먹는다. 1-2. 상어는 잡아먹은 물고기의 방향을 갖는다. 1-3. 방향을 유지한 채 범위 내에서 여러 개의 칸을 이동할 수 있다. (ex..

https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 풀이 요즘 마법사 상어 시리즈를 풀어보고있는데 파이어스톰 마법을 배웠다고 한다... 위 문제는 아래와 같은 과정을 거친다. 파이어스톰 단계를 L이라고 가정했을 때, (0, 0)을 시작으로 $2^{L}$x$2^{L}$ 크기의 부분 격자로 나눈다. 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 특정 칸에서 인접해있는 칸 중 얼음이 존재하는 칸이 3개 미만이라면 특정 칸의 얼음..

https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 풀이 위 문제는 맵 격자의 가운데 칸부터 토네이도가 이동을 시작한다. 한 번에 한 칸씩 이동하며 모래는 아래와 같은 비율로 흩날리게 된다. static double[] per = {1,1,2,2,7,7,10,10,5,0}; static int[][] sdx = { {-1,1,-2,2,-1,1,-1,1,0,0}, // 좌 {-1,-1,0,0,0,0,1,1,2,1}, ..

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 풀이 이번 문제는 설명에 너무 자세하게 적혀있어서 풀이할 게 없다. 문제에서 시키는대로 하면 된다. 우선 ArrayList 배열로 선언된 Student 에 학생의 번호와 좋아하는 학생의 번호를 넣어준다. 문제 1, 2, 3번의 조건을 쉽게 해결하려면 우선 순위 큐를 사용하면 된다. public static class Position implements Comparable{ int x; ..

https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 풀이 문제의 조건 및 구동 순서는 아래와 같다. 1. 벨트가 각 칸 위에 있는 로봇과 함께 움직인다. 2. 가장 먼저 벨트에 올라간 로봇부터 회전 방향으로 한 칸씩 이동한다. (이동하려는 칸의 내구도가 0 이상이며 로봇이 없을 경우) 3. 올리는 위치에 있는 칸의 내구도가 0이 아니면 로봇을 올릴 수 있다. 4. 위의 과정을 내구도가 0인 칸의 개수가 K개 이상일 때까지 반복..