본문 바로가기

문제 노트/백준

 (102)
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개이기에 각 쿼리 당 효율적인 알고리즘이 요구되는 문제입니다. 이 문제를 풀기 위해서는 우선, 절반 이상의 개수를 가지기 위해서 필요한 조건을 생각해보아야 합니다. 문제 해결하..
배열에서 이동( BOJ 1981 ) 문제 : https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 문제 파악하기 (1, 1)에서 (N, N)까지 이동하는 모든 경우 중 (최댓값-최솟값)이 가장 작은 경우를 구하는 문제입니다. 상하좌우 모든 방향으로 이동할 수 있으며, 100*100크기의 배열이기 때문에 모든 경우의 수를 구하는 건 불가능합니다. 그렇기에 적절하게 탐색의 범위를 조절해야 합니다. 문제 해결하기 문제를 해결하기 위해서는 (1, 1)에서 (N, N)까..
전구 끄기( BOJ 14927 ) 문제 : https://www.acmicpc.net/problem/14927 14927번: 전구 끄기 홍익이는 N x N 전구 판을 가지고 있다. 전구 판에는 각 칸마다 전구가 하나씩 연결되어 있다. 이 전구 판에서 하나의 전구를 누르면, 해당 전구를 포함하여 상하좌우의 총 5개 전구들의 상태가 변 www.acmicpc.net 문제 파악하기 불 켜진 전구를 효율적으로 끄는 방법을 찾는 문제입니다. 전구를 끄는 문제는 전통적으로 주변 전구들이 함께 영향을 받았는데 이번 문제 역시 하나의 전구를 작동시키면 주변 4방향(동서남북)의 전구 또한 영향을 받는 문제입니다. 이 문제를 해결하기 위해서는 전체적인 전구 상태를 보기 보다는 한 줄씩 나눠서 전구들을 확인해야 합니다. 문제 해결하기 우선, 전구는 항상 1번..
파일 합치기 3 문제 : https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 문제 파악하기 K개의 파일을 합쳐서 하나의 소설로 만들 때, 필요한 최소비용을 구하는 문제입니다. 이전 문제와 다른 점은 파일을 합칠 때, 연속하지 않은 파일 2개를 선택할 수 있다는 것입니다. 이전 문제는 항상 연속된 파일 2개를 선택해야 했지만 지금은 파일 2개의 위치가 어디있든 상관없이 하나의 파일로 합칠 수 있습니다. 그렇기에 이 문제는 단순하게 생각할 수 있습니다. 문제 해결..

티스토리툴바