본문 바로가기

문제 노트

 (155)
개미( BOJ 2136 ) 문제 : https://www.acmicpc.net/problem/2136 2136번: 개미 길이가 L(2 ≤ L ≤ 1,000,000,000)인 막대기 위에 N(1 ≤ N ≤ 100,000)마리의 개미들이 서로 다른 위치에 살고 있다. 개미들은 크기가 매우 작기 때문에 이 문제에서는 개미가 크기가 없는 점이라고 생각 www.acmicpc.net 문제 파악하기 길이가 L인 막대기 위에 있는 N마리의 개미 중 가장 늦게 떨어지는 개미의 번호와 시간을 구하는 문제입니다. N마리의 개미는 왼쪽 또는 오른쪽 방향으로 움직이며 서로 만나면 반대 방향으로 이동합니다. 개미들이 부딪히는 모든 경우를 시뮬레이션하는 방법을 가장 먼저 떠올릴 수 있지만 개미가 많아질수록 구현도 어려워지고 시간 복잡도 역시 증가합니다. 그..
유클리드 게임( BOJ 4342 ) 문제 : https://www.acmicpc.net/problem/4342 4342번: 유클리드 게임 유클리드 게임은 두 명이서 하는 게임이고, 자연수 2개로 시작한다. 동혁이와 동규는 유클리드 게임을 하려고 한다. 동혁이가 먼저 시작한다. 동혁이는 큰 수를 작은 수의 배수만큼 뺀다. 이때, www.acmicpc.net 문제 파악하기 주어진 두 개의 자연수를 사용하여 유클리드 게임을 했을 때, 선공을 하는 사람(동혁)이 이기는지 후공을 하는 사람(동규)이 이기는지 확인하는 문제입니다. 두 사람은 항상 최적의 방법으로 게임을 한다는 설명을 통해 우리는 시작부터 승자와 패자가 결정되었다는 걸 확인할 수 있습니다. 그럼 두 개의 숫자를 가지고 누가 이기는지 어떻게 알 수 있을까요? 이는 유클리드 게임을 분석하..
옥토끼는 통신교육을 풀어라( BOJ 17838 ) 문제 : https://www.acmicpc.net/problem/17383 17383번: 옥토끼는 통신교육을 풀어라!! 옥토끼가 이런 식으로 문제를 풀면 tncks0121은 옥토끼가 5, 10, 15, 20, 25, 30, 34분에 문제를 풀었으므로 최대 5분동안 휴식을 한 것으로 간주한다. www.acmicpc.net 문제 파악하기 옥토끼가 N개의 문제를 푸는데 필요한 시간 간격의 최댓값이 가장 작아지는 경우를 구하는 문제입니다. 옥토끼는 한 번에 2개의 문제를 풀 수 있으며, 선택한 문제는 끝까지 해결한다고 합니다. 입력된 예시(3 4 5 9 10 14 15)를 보면서 문제를 자세히 이해해보겠습니다. 만약 가장 단순하게 입력된 순서대로 문제를 선택해서 해결한다면 아래와 같은 결과가 나오게 됩니다. ..
게리멘더링( BOJ 28433 ) 문제 : https://www.acmicpc.net/problem/28433 28433번: 게리맨더링 길이 $N$인 수열 $A_1, A_2, \cdots, A_N$이 주어집니다. 이 수열을 원하는 개수의 연속된 구간으로 나누어서, 각 구간의 합을 계산합니다. 합이 양수인 구간의 개수가 합이 음수인 구간의 개수를 초과 www.acmicpc.net 문제 파악하기 합이 양수인 구간을 음수인 구간보다 많이 만들 수 있는지 판단하는 문제입니다. 각 테스트케이스마다 최대 200,000개의 숫자가 주어지기 때문에 단순히 모든 경우를 확인하는 전탐색 알고리즘보다 효율적인 알고리즘이 필요합니다. 다행히 문제를 잘 살펴보면 나름 규칙성을 찾을 수 있습니다. 그럼 어떤 규칙을 찾을 수 있을까요? 문제 해결하기 문제를 관찰..
하늘에서 떨어지는 1, 2, ... , R-L+1개의 별( BOJ 17353 ) 문제 : https://www.acmicpc.net/problem/17353 17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 욱제의 은밀한 취미 중 하나는 매일 밤하늘을 감상하는 것이다. 😓 욱제는 하늘의 별들이 다음과 같은 규칙들을 따르며 떨어지는 걸 관찰했다. 별이 떨어지는 위치는 N개의 점이다. 점은 순 www.acmicpc.net 문제 파악하기 주어진 N개의 수열을 대상으로 [ L, R ] 구간에 1, 2, ... , R-L+1의 값을 더하는 쿼리와 X 위치의 값을 구하는 쿼리를 수행하는 문제입니다. 수열의 범위가 최대 100,000개이며 쿼리의 수가 최대 100,000개이기 때문에 효율적인 자료구조가 필요합니다. 또한, 수행할 쿼리 역시 모든 구간에 동일한 값을 더하는 작업..
아이템 획득( BOJ 28216 ) 문제 : https://www.acmicpc.net/problem/28216 28216번: 아이템 획득 $N ≤ 2\,000$, $Q ≤ 2\,000$, $x_i ≤ 1\,000$, $y_i ≤ 1\,000$, $w_i ≤ 10$, 매 순간 자동차의 $x$, $y$좌표는 $1\,000$ 이하이다. www.acmicpc.net 문제 파악하기 자동차가 Q번 이동하면서 획득한 상자의 아이템 개수를 구하는 문제입니다. 자동차는 (1, 1) 위치에서 시작하며, 이동하면서 만나는 상자에서 항상 아이템을 얻을 수 있습니다. 상자와 이동하는 횟수 모두 최대 200,000번이기에 전탐색으로는 문제를 해결할 수 없습니다. 하지만 x와 y의 값이 최대 200,000이라는 범위 안이기 때문에 x와 y축을 기준으로 적절하게 상..
0과 1( BOJ 8111 ) 문제 : https://www.acmicpc.net/problem/8111 8111번: 0과 1 각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수를 아무거나 출력한다. 만약, 그러한 수가 없다면 BRAK을 출력한다. www.acmicpc.net 문제 파악하기 0과 1로 이루어졌으며 길이가 100 이하인 숫자 중 N의 배수를 구하는 문제입니다. 최대 길이가 정해져있지만 모든 경우를 확인하기에는 2100이라는 경우의 수는 너무 많습니다. 그렇기에 굳이 확인할 필요가 없는 숫자는 확인하지 않아도 되며, 이 때 사용할 수 있는 도구는 바로 나머지 연산입니다. 문제 해결하기 나머지 연산을 어떻게 활용하면 불필요한 탐색을 제거할 수 있을까요? 우리가 사용하는 숫자는 0과 1이며 나누는 숫자는 항상 N..
주유소( BOJ 28219 ) 문제 : https://www.acmicpc.net/problem/28219 28219번: 주유소 KOI 국가는 $N$개의 마을로 이루어져 있다. 각 마을에는 $1$번 마을, $2$번 마을, $\cdots$, $N$번 마을과 같이 번호가 붙어 있다. 그리고 도로가 $N - 1$개 있는데, 각각의 도로는 서로 다른 두 마을을 잇 www.acmicpc.net 문제 파악하기 N개의 마을에 필요한 주유소의 최소 개수를 구하는 문제입니다. N개의 마을은 (N-1)개의 도로로 연결되어 있으며, 길이가 K인 두 마을 사이의 경로에는 꼭 1개 이상의 주유소가 있어야 합니다. 문제 설명에서 (N-1)개의 도로로 연결되어 있으며, 모든 마을 사이의 경로는 유일하게 존재한다는 점을 통해 N개의 마을은 트리 형태로 연결되어 ..

티스토리툴바