두부의 코딩일기

https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 풀이 브루트포스를 이용해서 푸는 문제다. '각 사람의 덩치 등수는 몇 등인가?' 문제에서의 덩치가 큰 기준은 키와 몸무게가 모두 비교하는 대상보다 클 경우다. 키와 몸무게를 담을 수 있는 배열을 생성 후에 2중 for문을 이용해서 본인을 제외한 모두와 비교하여 rank 값을 출력해줬다. 문제에서 rank는 본인보다 덩치가 큰 사람 수 + 1 이기 때문에 rank 변수는 1로 초기화해주..

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/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 풀이 공의 색깔과 크기를 비교해서 i번째 공으로 잡아먹을 수 있는 공들의 크기 합을 구하는 문제이다. 완전 탐색으로 접근하면 공의 개수가 200,000까지의 크기를 가지므로 시간 초과가 발생할 것이다. 따라서 위 문제는 누적합과 정렬을 이용해서 해결해야한다. 누적합을 사용하기 위해서는 공의 크기가 작은 순으로 정렬을 해주어야한다. public static class B..

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/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 처음엔 완전 탐색으로 접근했다가 메모리 초과가 발생했다. 2중 for문을 이용해서 모든 경우의 수를 변경해준다. 이 과정에서 visited[number][cnt] 2차원 배열로 자리를 바꾼 후에 생기는 중복된 수를 제거했다. 중복된 수를 제거할 때는 변경 횟수도 중요하다. 변경된 숫자가 같더라도 1번 변경했을 때 나온 A와 2번 변경했을 때 나오는 B는 전혀 다르다. 그렇기 때문에 변경 횟수도 방문 여부를 체크해줄 때 꼭 필요하다. for (int i=0; i

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개 미만이라면 특정 칸의 얼음..