본문 바로가기

Beakjoon

 (14)
[Beakjoon Online Judge] 11047- 동전 0(C++) I 문제 소개 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. II 문제 풀이 사실 너무 간단해서 뭐라고 붙일 문제는 아니다. 다만 앞으로 탐욕법과 관련된 문제를 풀어보려해서 가장 기초적인 문제를 찾아 풀어보았다...
[Beakjoon Online Judge] 2869 - 달팽이는 올라가고 싶다(C++) 문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) 출력 첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다. 어쩌면 초등학교 수학책 맨 뒤에 항상 있었던 "문제푸는 방법찾기"라는 단원에 있었을지도 모르는 문제겠다. 가장 처음 생각나는 건, 현재 높이를 나타내는 변수를 만들고, 이를 반복문 속에서 비교하..
[Beakjoon Online Judge] 1850 - 최대공약수(C++) 문제 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A가 111이고, B가 111111인 경우에는 최대공약수가 111이다. 입력 첫째 줄에 두 자연수 A와 B를 이루는 1의 개수가 주어진다. 입력되는 수는 2^63보다 작은 자연수이다. 출력 첫째 줄에 A와 B의 최대공약수를 출력한다. 정답은 천만 자리를 넘지 않는다. 라는 문제다. 처음에는 그냥 최대공약수를 구하는건줄 알았는데, 3 6을 입력받는데 6보다도 큰 111을 출력한다고? 문제를 잘못봤었다. 2^63이면 int에는 못담고 long long을 써야하겠다 싶었고 그정도 큰 수는 최대공..
[Beakjoon Online Judge] 10951 - A+B - 4(C++) 문제 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 A와 B가 주어진다. (0 < A, B < 10) 출력 각 테스트 케이스마다 A+B를 출력한다. 얼핏 보면 굉장히 간단한 문제다. 입력이 1 2 3 4 5 6 라고 주어지면, "3 7 11"을 출력하면 되는 것이다. 그런데 의문스러운 부분이 있다. 이렇게 간단한 문제인데 정답 비율이 30%대이다. 이것은 어딘가 함정이 숨어져 있다는 것이다. 그래서 코딩을 시작하는데, 난관이 존재했다. 입력을 while문이나 for문같은 반복문으로 받을건데, "입력을 몇 번 받는지" 알 수 없다. 문제에서도 "여러 개의 테스트 케이..
[Beakjoon Online Judge] 1094 - 막대기(C++) 문제 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대를 만들려고 한다. 막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 지민이는 아래와 같은 과정을 거쳐서 막대를 자르려고 한다. 지민이가 가지고 있는 막대의 길이를 모두 더한다. 처음에는 64cm 막대 하나만 가지고 있다. 이때, 합이 X보다 크다면, 아래와 같은 과정을 반복한다. 가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다. 만약, 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 X보다 크거나 같다면, 위에서 자른 막대의 절반 중 하나를 버린다. 이제, ..
[Beakjoon Online Judge] 1074 - Z(C++) 문제 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다. 다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다. N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 문제는 위와 같다. 재귀적인 움직임을 보이기 때문에 규칙을 만들어 해당 위치까지 하나씩 찾아가면 풀 수 있겠으나, 코딩테스트 특성상 "시간 초과"라는 무서운 친구가 있기 때문에 조금 고차..

티스토리툴바