본문 바로가기

문제 노트

 (157)
다리( BOJ 9006 ) 문제 : https://www.acmicpc.net/problem/9006 문제 파악하기 왼쪽 집에서 오른쪽 집으로 가는 모든 거리의 합을 최소화하기 위해 다리를 놓아야 할 곳을 찾는 문제입니다. 다리의 길이는 항상 2이기 때문에 다리 길이에 대해서는 신경쓸 필요가 없으며, 어느 위치에 다리를 놓을 것인지만 생각하면 됩니다. 다만, N의 최대 범위가 106이며, 입력되는 집의 위치가 -107 ~ 107이기 때문에 단순히 모든 경우를 탐색하는 방법으로는 절대 해결할 수 없습니다. 대신, 중복되는 계산을 효과적으로 줄여서 정답을 찾을 수 있습니다. 문제 해결하기 만약 우리가 h 위치에 다리를 놓았다고 가정하면, 우리가 최솟값을 구해야할 수식 f(h)는 다음과 같습니다. 참고로 수식에서 배열 a과 b는 각각 ..
동전 문제( BOJ 1398 ) 문제 : https://www.acmicpc.net/problem/1398 1398번: 동전 문제 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 초콜릿의 가격이 주어진다. 가격의 1015보다 작거나 같은 자연수이다. www.acmicpc.net 문제 파악하기 주어진 초콜릿의 가격을 만들 수 있는 동전의 최소 개수를 구하는 문제입니다. 모든 동전이 우리나라 동전 체계처럼 약수 관계를 가지고 있다면 간단하게 사용할 수 있는 가장 큰 동전부터 사용하는 그리디 기법을 사용할 수 있습니다. 하지만 문제에 제시된 동전들은 약수 관계를 가지고 있지 않습니다. 이 경우에는 가치가 큰 동전부터 사용하는 것이 최적이 아닙니다. 예를 들어 초콜릿의 가격이 30원이라고 하면, 단순히 그리디 기법을 ..
게리맨더링( BOJ 17471 ) 문제 : https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 문제 파악하기 입력된 그래프를 2개의 구역으로 나눠 인구수의 차이를 최소로 하는 경우를 찾는 문제입니다. 마을의 개수(N)이 작기 때문에 모든 경우의 수를 탐색해도 충분한 문제입니다. 각각의 마을을 0번 혹은 1번 선거구로 설정한 다음, 깊이 우선 탐색과 비트마스킹을 활용하면 문제를 풀 수 있습니다. 문제 해결하기 우선, N개의 마을을 0번 혹은 1번 선거구로 나눌 수 있는 모든 경우의 수를 만들어봅시다. 재..
창업( BOJ 16890 ) 문제 : https://www.acmicpc.net/problem/16890 16890번: 창업 입력은 길이가 N(1 ≤ N ≤ 300,000)인 문자열 두 개로 이루어져 있다. 모든 문자열은 알파벳 소문자로만 이루어져 있다. 첫 번째 줄에 주어지는 문자열은 구사과가 고른 문자이고, 두 번째 줄에 주 www.acmicpc.net 문제 파악하기 N개의 문자로 이루어진 문자열 2개에서 값을 하나씩 순서대로 가져와서 새로운 문자열을 만드는 문제입니다. 다만, 첫 번째 문자열에서 가져온 문자로는 항상 사전 순으로 앞서게 만들어야 하며, 두 번째 문자열에서 가져온 문자로는 항상 사전 순으로 뒤에 오게 만들어야 합니다. 모든 경우의 수를 찾는 방법을 가장 먼저 떠올릴 수 있지만 N의 값이 최대 300,000개이기 ..
스타트링크 타워( BOJ 1089 ) 문제: https://www.acmicpc.net/problem/1089 1089번: 스타트링크 타워 스타트링크 타워는 총 10N개 층이 있는 고층 건물이고, 0층부터 10N-1층으로 번호가 매겨져 있다. 층 번호를 숫자 N개로 표현한다. 숫자 N개로 층 번호를 표시할 수 없는 경우 앞에 0을 채운다. 숫자 www.acmicpc.net 문제 파악하기 엘리베이터의 전구를 파악해서 나올 수 있는 모든 숫자의 평균을 구하는 문제입니다. 10-5까지의 오차를 허용하기 때문에 맨 마지막에 평균을 구해주면 실수 값을 처리하는데 크게 문제가 없는 문제입니다. 이 문제에서 조금 까다로운 부분은 엘리베이터의 층을 표현하는 부분입니다. 층과 층 사이는 '.'으로 구분되어 있으며, 숫자들은 0부터 9까지 서로 다른 모습을 ..
자물쇠( BOJ 2478 ) 문제 : https://www.acmicpc.net/problem/2478 2478번: 자물쇠 처음 k-왼쪽밀기의 k를 첫째 줄에, (p,q)-구간뒤집기의 p와 q를 빈칸을 사이에 두고 둘째 줄에, 그리고 마지막 k-왼쪽밀기의 k를 셋째 줄에 출력한다. 만일 답이 여럿일 경우에는 그 중 하나만 출력 www.acmicpc.net 문제 파악하기 주어진 수열을 만들기 위해 필요한 k-왼쪽밀기와 (p, q)-구간뒤집기 작업을 구하는 문제입니다. 모든 자물쇠는 [ k-왼쪽밀기 > (p, q)-구간뒤집기 > k-왼쪽밀기 ] 순서로 작업이 이루어지기 때문에, 우리는 반대로 [ k-오른쪽밀기 > (p, q)-구간뒤집기 > k-오른쪽밀기 ] 순서로 작업을 하여 정렬된 수열의 상태(1, 2, 3, ... , n)를 만들면..
수 지우기( BOJ 1467 ) 문제 : https://www.acmicpc.net/problem/1467 1467번: 수 지우기 첫째 줄에 세준이가 가지고 있는 N자리의 수가 주어진다. N은 1,000보다 작거나 같은 자연수이다. 둘째 줄에 세준이가 지울 숫자들이 공백 없이 주어진다. 지울 숫자의 개수는 N보다 작으며, 항상 www.acmicpc.net 문제 파악하기 세준이가 가지고 있는 숫자 중 제시된 지울 숫자들을 지워서 만들 수 있는 가장 큰 숫자를 구하는 문제입니다. 문제 자체는 이해하기 어렵지 않지만 문제를 해결할 전략을 세우는데 생각이 필요한 문제입니다. 문제를 해결하기 위해 우리가 초점을 맞춰야 할 핵심요소는 바로 큰 수의 조건입니다. 큰 수가 되기 위해서는 큰 숫자가 왼쪽에 있어야 합니다. 이 점에 주목하면 문제를 해결..
아우으 우아으이야!!( BOJ 15922 ) 문제 : https://www.acmicpc.net/problem/15922 15922번: 아우으 우아으이야!! N개의 선분을 모두 그렸을 때, 수직선 위에 그어진 선분 길이의 총합을 출력한다아아어으잉에애야우아으아이아야아아아아아아이야!!! www.acmicpc.net 문제 파악하기 N개의 선분을 수직선 위에 그렸을 때, 그어진 모든 선분의 길이의 합을 구하는 문제입니다. 입력에 따라 선분들이 겹치는지 확인할 필요가 있습니다. 다행히 선분의 개수가 100,000개이기 때문에 충분히 정렬을 사용할 수 있습니다. 문제 해결하기 모든 선분을 왼쪽 좌표 기준으로 정렬하면 가장 왼쪽에 위치한 선분부터 탐색을 시작할 수 있습니다. 가장 왼쪽의 선분의 왼쪽과 오른쪽을 각각 (l, r)으로 설정할 수 있으며, 다음 선분..

티스토리툴바