문제 링크https://www.acmicpc.net/problem/17086 문제 요약임의의 점 \((i, j)\)의 안전거리는 \((i, j)\)에서 시작해서 아기 상어가 있는 곳까지의 최소 거리를 의미한다. 여기서 거리는 인접한 8방향(상하좌우 및 대각선)으로 이동한 칸 수로 계산한다. 격자판 위의 모든 점들 중에서 안전거리가 최대인 값을 찾아 출력하는 것이 이 문제의 목표이다. 문제 풀이기본적인 풀이너비 우선 탐색(이하 BFS)을 이용하면 임의의 점 \((i, j)\)에서 가장 가까운 아기 상어까지의 거리를 계산할 수 있다. 그리고 N과 M의 크기가 작으므로 모든 점들에 대해서 BFS를 한 번씩 돌려도 제한시간 내에 충분히 답을 구할 수 있다. 아래 더보기 버튼을 누르면 이 방법으로 푼 코드를 볼..
문제 링크https://www.acmicpc.net/problem/9376 문제 요약두 죄수 A, B가 최소한의 문을 열어 감옥에서 탈출하려고 한다. 한 죄수가 문을 열면, 그 문은 계속 열려 있어서 다른 죄수도 그 문을 이용할 수 있다.(원래 문제에서는 감옥 밖에 있는 상근이가 특별한 기술을 이용해 문을 열어준다고 되어 있지만, 문제를 더 쉽게 이해할 수 있게 내용을 살짝 바꿨다.) 문제 풀이가장 먼저 떠오르는 생각은 두 죄수의 상태를 동시에 관리하는 것이다. 하지만 죄수가 있을 수 있는 장소는 1만 곳이고, 이를 두 죄수의 상태로 표현하면 1억 가지의 경우의 수가 생긴다. 여기에 탈출을 위해 이용한 문의 개수까지 고려한다면 이 방법은 문제를 제한 시간 내에 풀 수 있는 방법이 아니다. 경우의 수 나누..
문제 링크https://www.acmicpc.net/problem/10021 문제 요약농부 John은 가뭄 때문에 N개의 농지에 물을 공급하기 위한 수로를 설치하려고 한다. 각 농지는 2차원 평면 위의 점 \((x_i, y_i)\)로 나타내며, 서로 다른 두 농지 \(i\)와 \(j\)를 연결하는 수로를 건설하는 비용은 \((x_i - x_j)^2 + (y_i - y_j)^2\)으로 계산한다. 이 문제는 모든 농지가 서로 물을 공급받을 수 있도록 수로를 설치하는 최소 비용을 계산하는것이 목표다. 제약 사항이 하나 있다면 수로를 건설하는 업자가 수로 건설 비용이 C 이상이 되는 것만 설치한다는 것이다. 문제 풀이이 문제에서 농지는 그래프의 노드로, 수로는 간선으로 모델링 할 수 있다. 이렇게 그래프로 모델..
문제 링크https://www.acmicpc.net/problem/17404 문제 요약N개의 집을 다음 두 개의 규칙에 맞게 빨강, 초록, 파랑 중 하나로 칠해야 한다.인접한 두 집의 색이 달라야 한다.1번 집과 N번 집의 색이 달라야 한다.각 집을 특정 색으로 칠하는 비용이 주어졌을 때, 모든 집을 규칙에 맞게 칠할 때 드는 최소 비용을 구하는 문제이다.원래 문제에는 규칙이 세 개 있지만, 이해를 돕기 위해 두 개로 정리했다. 문제 풀이이 문제는 동적 계획법(dynamic programming)을 이용해 해결할 수 있다. 먼저, 부분 문제를 해결할 수 있는 함수를 정의한다. \(findMinCost(idx, prevColor) =\) idx - 1번째 집을 prevColor로 칠했을 때, idx번째 ..
문제 링크https://www.acmicpc.net/problem/1022 문제 요약반시계 방향을 따라 소용돌이 모양으로 숫자를 채운 뒤, 주어진 범위의 숫자를 포맷에 맞게 출력하는 문제 문제 풀이이 문제를 푸는 방법에는 실제로 소용돌이를 만들어보는 시뮬레이션 방법과 특정 좌표의 숫자를 구할 수 있는 규칙을 찾는 방법 두 가지가 있다. 이 문제를 풀기 위해 접근할 때 보통 두 번째 방법을 많이 생각하는 것 같다. 하지만 입력으로 주어지는 수의 제한 범위와 현대 컴퓨터의 연산속도를 이용하면 직접 시뮬레이션을 돌려 푸는 방법도 있다는 것을 소개하고 싶다.풀이 1. 시뮬레이션모눈종이에 소용돌이 모양으로 숫자를 채우는 시물레이션을 돌려보는 상상을 해보자. 입력으로 주어지는 좌표의 최솟값은 -5,000이고 최댓값..
문제 링크 https://www.acmicpc.net/problem/1111 문제 요약점화식 \(x_{i+1} = x_i * a + b\) 으로 만들어진 길이 \(N\)의 수열이 주어진다. \(a\), \(b\)를 찾아 수열의 다음 항을 출력하는 문제이다. 문제 번호도 그렇고 제목도 그렇고 뭔가 쉬워보이는 냄새가 난다. IQ Test 정도는 뭔가 쉽게 통과할 것 같은 근자감도 생긴다. 그렇게 9년 전의 나는 쉬운 마음으로 1111번에게 도전했다 참패했다. 9년이 지난 지금의 나는 어떨까? 쉽진 않았지만 그래도 어찌저찌 9년 전 참패는 만회할 수 있었다. 구미가 당기는 번호, 쉬운 제목으로 사람을 현혹시키고 패배의 감정을 맛보게 해주는 악마의 문제 백준 1111번 풀이를 적어본다. 문제 풀이세 개의 연속된..
백준에서 풀만한 문제가 뭐가 있다 어슬렁거리다 과거의 내가 풀지 못했던 문제를 지금 내가 푼다면 맞출 수 있을까 궁금해졌다. 슬프게도 시도했지만 맞지 못한 문제가 많아 숫자가 작은 것부터 다시 시도해 봤다. 그래서 선택한 1039번!! 무려 9년 전, 그러니까 2014년에 시도하고, 2015년에 다시 한번 시도하고 나에게 잊혔던 1039번이 다시 나에게 다가왔다. 과연 지금의 나는 과거의 나보다 더 강해졌을까 긴장되는 마음으로 문제를 다시 읽어봤는데 다행히 과거의 나보다는 더 강해진 것 같아 이렇게 풀이를 작성해 본다.문제 링크https://www.acmicpc.net/problem/1039 문제 요약주어진 정수 \(N\)에서 서로 다른 두 자릿수의 위치 \(i\), \(j\)를 선택하여 숫자를 서로 교..
1. 방 배정 https://www.acmicpc.net/problem/13300 학생들을 학년별, 성별로 한 방에 배정하려고 하는데 필요한 최소 방의 개수를 구하는 문제다. 문제에서 요구하는 대로 학년별, 성별로 인원을 센 다음에 각각에 대해 최소로 필요한 방의 개수를 센 뒤 더해주면 된다. 이는 나눗셈과 나머지 연산으로 쉽게 구할 수 있다. #include int n, k, s, y, C[7][2]; int main() { scanf("%d%d", &n, &k); while (n--) { scanf("%d%d", &s, &y); ++C[y][s]; } int ans = 0; for (int i = 1 ; i
문제 링크 https://www.acmicpc.net/problem/5626 문제 요약 현재 제단의 상태가 주어진다. 도둑이 훔쳐간 부분은 -1이고 남아있는 부분은 정수로 표현이 되어있다. 이 때 가능한 초기 제단의 경우의 수를 구하는 문제다. 문제에서 초기 제단을 만드는 방법은 주어진다. 문제 풀이 모든 열의 초기값은 0이다. 이 때 한가지 연산을 할 수 있다. 같은 높이를 가지는 연속하는 열들을 선택한다. 그리고 선택한 연속된 열 중 처음 열과 가장 끝 열을 제외한 모든 열의 높이를 1씩 높인다. 이 연산을 사용해서 제단을 만들어 나갈 수 있다. 이 연산을 잘 생각해 본다면 두가지 통찰을 얻을 수 있다. 1. 첫 번째 제단과 마지막 열의 높이는 0이다. 2. 인접한 두 열의 높이차는 최대 1이다. 이..
문제 링크 https://www.acmicpc.net/problem/1637 문제 요약 정수가 여러개 모여있는 정수더미가 있다. 이 때 정수더미 안에서 홀수개 들어있는 특정 정수를 찾는 문제다. 홀수개 들어있는 정수의 수는 최대 한개이며 없을수도 있다. 문제 풀이 이 문제는 정수가 직접 주어지는게 아니라 정수더미 안에 들어있는 수들의 규칙이 주어지고 이를 통해 홀수개 들어있는 정수를 찾아야 하기 때문에 단순 시뮬레이션으로는 풀수가 없다. 그렇다면 어떻게 접근해야 할까? 우선 예제의 수들을 한번 직접 계산해보자. 직접 계산해 본다면 숫자 4가 3개 들어있어서 답이 됨을 알 수 있다. 이것만으로 일정한 규칙을 찾을수가 없다. 하지만 이들 수의 누적합을 계산해 본다면 특정 규칙을 찾을 수 있다. 위 표를 잘 ..
MO's algorithm은 온라인으로 풀기 힘든 쿼리 문제를 오프라인으로 쉽게 풀 수 있게 해주는 알고리즘이다. MO's algorithm은 쿼리를 정렬한 뒤 정렬된 순서대로 처리를 한다. 이론은 이게 끝이다. 이론만 들어서는 아마 문제에 어떻게 적용해야 할 지 감이 안올것이다. 그럼 연습문제를 풀면서 MO's algorithm을 익혀보도록 하자. 연습문제는 https://www.acmicpc.net/problem/13547에서 풀 수 있다. 구간에 존재하는 서로 다른 수의 개수연습 문제는 아래와 같다. 자연수로 이루어진 \(A_1,\ A_2,\ A_3,\ ...\ ,\ A_{N-1},\ A_{N}\)시퀀스가 있다. 이 때 다음 쿼리를 처리해야 한다.1. \(x,\ y\ (1 \le x \le y \l..
문제 링크 https://www.acmicpc.net/problem/2365 문제 요약 \(N*N\)행렬의 각 열들의 합과 각 행들의 합이 주어졌을 때 원본 행렬을 복구하는 문제다. 하지만 아무렇게나 복구하는것이 아니라 행렬에 써져있는 숫자의 최댓값이 최소가 되도록 하고 싶다. 이 때 행렬을 복구한 뒤 출력한다. 문제 풀이 이 문제는 https://www.acmicpc.net/problem/1960와 상당히 유사한 문제다. 먼저 이 문제를 풀어보는것을 권장한다. 이 문제의 풀이를 알고 있다는 전제조건 하에 풀이를 서술하려 한다. 이 문제의 풀이는 링크에서 볼 수 있다. 이 문제에서 달라진 점은 각 행렬에 들어갈 수 있는 값이 0또는 1이 아니라 내가 정할 수 있다는 점이다. 만약 내가 원본 행렬에 존재하..
