UP

문제 풀기 : 2251번 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 문제 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 때, 한 물통이 비거나 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수..

문제 풀기 : 1963번 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 문제 입력은 항상 네 자리 소수만(1000 이상) 주어지며 주어진 두 소수 A에서 B로 바꾸는데 필요한 최소 단계를 구한다. 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 한다. 문제풀이 모든 경우의 수를 전부 찾는 완전탐색이면서 BFS를 사용한 문제이다. 우선 네 자리 수인 9999까지의 모든 수를 완전탐색을 통해서 소수인지 판별을 한다. 그 다음은 각 자리수마다 숫자(0 ~ 9)를 바꾸어 가며 소수인 수는 큐에 넣어서 또 다시 자릿수를 바..

문제 풀기 : 10819번 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 문제 N개의 정수로 이루어진 배열 A의 정수들을 적절히 배치시켜 다음 식의 최댓값을 구한다. |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| (3 ≤ N ≤ 8, -100 ≤ A[N] ≤ 100) 문제풀이 모든 경우의 수를 전부 찾는 완전탐색 문제이다. N개의 정수를 오름차순으로 정렬해서 차이를 구하면 최소값을 구할 수 있지만 최대값을 구하려면 전체의 경우의 수를 구해야 한다. N개의 정수들에 대한 ..

문제 풀기 : 9095번 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구한다. (0 < n < 11) 문제풀이 모든 경우의 수를 전부 찾는 완전탐색 문제이다. 1 : 1 (1개) 2 : 1+1 / 2 (2개) 3 : 1+1+1 / 1+2, 2+1 / 3 (4개) 4 : 1+1+1+1 / 1+1+2, 1+2+1, 2+1+1 / 2+2 / 1+3, 3+1 (7개) 5 : 1+1+1+1+1 / 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1 / 1+2+2, 2+1+2, 2+2+1 / 1+1+3, 1+3+1, 3+1+1 / 2+3, 3+..

문제 풀기 : 1476번 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 문제 수 3개를 이용해서 연도를 나타낸다. 지구, 태양, 달을 나타내는 수이며 지구의 수는 E, 태양의 수는 S, 달의 수는 M이다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) 제한된 범위를 넘어가면 1로 초기화된다. E, S, M이 주어졌을 때 연도로 몇 년인지 구한다. 예) 1 15 15 = 16년 문제풀이 모든 경우의 수를 전부 찾는 완전탐색 문제이다. 전체를 탐색하는데 15 x 28 x 19 = 7980 가지 밖..

문제 풀기 : 1744번 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제 길이가 N인 수열이 주어졌을 때, 수열의 두 수를 묶고 수열의 합을 구한다. 위치에 상관없이 수를 묶을 수 있다. 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 묶은 수는 서로 곱한 후에 더한다. 예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2x3)+(4x5) = 27이 되어..

문제 풀기 : 1931번 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만든다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있다. 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾는다. 단, 회의는 한번 시작하면 중간에 중단될 수 없다. 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. (이 경우에는 시작하자마자 끝나는 것으로 생각한다.) 문제풀이 최적의 해를 구하는 그리디 문제이다. 회의실을 최대로 사용하려면 회의가 끝나는 시간이 짧은 순..

문제 풀기 : 11399번 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우 [1, 2, 3, 3, 4] 순으로 출력하면 각 사람이 돈을 인출하는데 필요한 시간의 합은..