본문 바로가기

문제 노트

 (157)
대기업 승범이네( BOJ 17831 ) 문제 : https://www.acmicpc.net/problem/17831 17831번: 대기업 승범이네 첫 번째 줄에 판매원들의 수 N(2 ≤ N ≤ 200,000)이 주어진다. 판매원들은 1번, 2번, …, N번으로 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 2번 판매원부터 N번 판매원의 사수가 순서대 www.acmicpc.net 문제 파악하기 승범이네 회사의 사원들 중 멘토와 멘티를 적절하게 선택해서 최대의 시너지 효과를 구하는 문제입니다. 승범이네 회사 구조는 트리 구조로 되어있으며 사수와 부사수 관계를 가지고 있는 사원을 멘토-멘티로 선정할 수 있습니다. 결국 이 문제는 현재 노드와 자식 노드를 멘토-멘티로 선정할 것인지, 아니면 현재 노드를 제외할지 탐색해야 하는 문제로 바꿀 ..
Degree Bounded Minimum Spanning Tree( BOJ 20927 ) 문제 : https://www.acmicpc.net/problem/20927 20927번: Degree Bounded Minimum Spanning Tree 제약에 맞는 Spanning Tree가 존재한다면 첫 번째 줄에 YES를 출력하여라. 이후 해당 Spanning Tree 의 간선을 $N-1$개의 줄에 걸쳐 출력한다. 간선을 출력하는 순서는 상관없으며, 각 간선을 출력할 때는 www.acmicpc.net 문제 파악하기 N개의 정점을 모두 연결하는 트리 중 가중치의 값이 가장 작은 트리의 모양을 찾는 문제입니다. 얼핏 보면 Spanning Tree 알고리즘 문제처럼 보이지만 이 문제는 한 가지 조건이 더 주어집니다. 바로 각각의 노드가 가질 수 있는 차수가 제한되어 있습니다. 그렇기에 기존의 크루스칼..
Pizza( Atcoder 238-B ) 문제 : https://atcoder.jp/contests/abc238/tasks/abc238_b B - Pizza AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 문제 파악하기 pizza를 주어진 각도만큼 회전시키고 잘랐을 때, 가장 큰 피자의 각도를 구하는 문제입니다. 피자의 각도는 0˚ ~ 359˚까지 있으며, 동일한 위치를 다시 자르지 않는다는 점을 고려하면 문제를 해결할 수 있습니다. 문제 해결하기 동일한 위치를 다시 자르지 않기에 우리는 0˚ ~ 359˚까지 배열을 사용해서 잘린 적이 있는지 확인하면 됩니다. ..
Optimization is Freaky Fun( BOJ 17417 ) 문제 : https://www.acmicpc.net/problem/17417 17417번: Optimization is Freaky Fun 첫 번째 줄부터 Q개의 줄에 걸쳐, 교준이의 프로그램의 출력 결과를 출력한다. www.acmicpc.net 문제 파악하기 입력받은 Q개의 쿼리를 처리하는 문제입니다. 쿼리는 N, S, E를 입력받으며, 구간 [S, E] 사이의 모든 자연수 i를 N으로 나눈 값([N/i])의 합을 구하는 문제입니다. 입력되는 N, S, E 자체가 최대 1012이기 때문에 단순한 반복문으로는 해결할 수 없습니다. 또한, 각각의 서브태스크의 조건이 다르기 때문에 시간에 맞춰 문제를 해결하기 위해서는 입력되는 쿼리의 특징에 따라 다른 알고리즘이 필요합니다. 예를 들어 서브태스크 2와 4를 ..
Celebrity( BOJ 23259 ) 문제 : https://www.acmicpc.net/problem/23259 23259번: Celebrity 첫째 줄에 아름다운 별의 수를 출력한다. www.acmicpc.net 문제 파악하기 주어진 N개의 그래프 중 동형인 그래프가 없이 유일한 모양인 그래프의 개수를 찾는 문제입니다. N은 최대 10,000개이지만 다행히 입력되는 모든 그래프의 정점은 항상 5개이기 때문에 모든 경우의 수를 확인하여 문제를 해결할 수 있습니다. 문제 해결하기 우선, 그래프가 동형인지 아닌지 확인하는 방법부터 찾아야 합니다. 그래프가 서로 동형이란 의미는 연결된 정점의 상태가 동일하다는 의미입니다. 문제에서 확인할 수 있듯이 별 A와 별 B는 달라보이지만 잘 보면 정점 간 연결된 상태가 똑같습니다. 이처럼 정점 간 연결된..
타일 채우기 2( BOJ 13976 ) 문제 : https://www.acmicpc.net/problem/13976 13976번: 타일 채우기 2 첫째 줄에 N(1 ≤ N ≤ 1,000,000,000,000,000,000)이 주어진다. www.acmicpc.net 문제 파악하기 3xN 크기의 벽을 1x2 크기의 타일로 채우는 경우의 수를 구하는 문제입니다. 2xN 크기의 벽을 채우는 문제의 심화된 버전이라고 할 수 있습니다. 하지만 문제를 해결하는 과정은 2xN 크기의 벽을 채우는 문제와 동일한 방식으로 해결할 수 있습니다. 이전 상태를 사용할 수 있는 경우가 총 몇 가지인지 확인해서 점화식을 세우면 문제를 해결할 수 있습니다. 문제 해결하기 이렇게 타일을 채우는 문제는 가장 작은 경우부터 하나씩 확인해보면 됩니다. 여기서 중요한 점은 사용하..
거스름돈( BOJ 14916 ) 문제 : https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제 파악하기 2원과 5원을 사용해서 N원을 만드는 방법 중 동전을 가장 적게 사용하는 방법을 찾는 문제입니다. 아쉽게도 5원부터 먼저 사용하는 방법으로는 문제를 풀 수 없습니다. 예를 들어 6원 같은 경우, 5원을 먼저 사용하는 방법으로는 해답을 찾을 수 없습니다. 따라서, 그리디 방식이 아닌 모든 경우를 고려하는 동적 프로그래밍이 필요합니다. 문제 해결하기 N원을 만들기 위해서는 2가지 조건 중 하나만 만족하면 됩니다. (N-2)원을 만들 수 있거나 (N-5)원을 만들 수 있으면 됩니다. 따라서, 우리는..
백설공주와 난쟁이( BOJ 2912 ) 문제 : https://www.acmicpc.net/problem/2912 2912번: 백설공주와 난쟁이 첫째 줄에 난쟁이의 수 N과 모자 색상의 수 C가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ C ≤ 10,000) 둘째 줄에는 각 난쟁이가 쓰고 있는 모자의 색상이 줄을 서 있는 순서대로 주어진다. 셋째 줄에는 사진 www.acmicpc.net 문제 파악하기 구간 [a, b]사이의 숫자 중 절반 이상의 개수를 가진 숫자가 있는지 없는지 판단하는 문제입니다. 데이터의 개수는 총 300,000개이며 쿼리의 개수는 10,000개이기에 각 쿼리 당 효율적인 알고리즘이 요구되는 문제입니다. 이 문제를 풀기 위해서는 우선, 절반 이상의 개수를 가지기 위해서 필요한 조건을 생각해보아야 합니다. 문제 해결하..

티스토리툴바