CEO

문제 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 풀이 카드 구매하기에서는 구매하고자 하는 카드를 최대값으로 구매하는 문제였다. 이와 달리 카드 구매하기 2는 가장 최소 값으로 카드를 구매할 경우에 발생하는 금액을 반환하는 문제이다. 카드 구매하기와 동일한 방법으로 풀며, 약간의 코드를 수정하면 이 문제도 쉽게 풀 수 있다. 코드 if __name__ == '__main__': N = int(input()) card = [0] + list(map(int, input().split())) memo = [0]..

문제 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 풀이 이 문제를 효율적으로 풀기 위해서는 메모이제이션(Memoization)을 활용하여야 한다. 문제의 예제와 같이 1 5 6 7이 입력되는 경우 카드 3개 까지 구매할 수 있는 경우의 수는 다음과 같다. 카드 1개 구매 : 1개 들어있는 카드 팩 카드 2개 구매 : (1개 들어있는 카드 팩) * 2, 2개 들어있는 카드 팩 카드 3개 구매 : (1개 들어있는 카드 팩) * 3, 2개 들어 있는 카드 팩 + 1개 들어 있는 카드백, 3개 들어 있는 카드팩 즉 ..

1, 2, 3 더하기 시리즈 1, 2, 3 더하기 1, 2, 3 더하기 2 1, 2, 3 더하기 3 1, 2, 3 더하기 4 1, 2, 3 더하기 5 1, 2, 3 더하기 6 1, 2, 3 더하기 7 1, 2, 3 더하기 8 1, 2, 3 더하기 9 문제 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 www.acmicpc.net 문제 풀이 이전에 풀었던, 11726 2xn 타일링, 11727 2xn 타일링 2과 같이 어떠한 경우의 수가 있는지 파악하는 것이 중요하다..

문제 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 문제 풀이 이 문제는 2 x n 타일링 문제에서 2 x 2 타일이 추가 되어, 사용할 수 있는 타일이 2 x 1, 1 x 2, 2 x 2로 3개인 경우에 2 x n의 공간에 타일을 붙일 수 있는 경우의 수를 구하는 문제이다. 그림 1을 보면, n이 증가함에 따라 1, 3, 5, 11, 21과 같은 규칙을 보이는 것을 알 수 있으며 이를 식으로 나타내면 `f(n) = f(n - 1) + 2 * f(n - 2)`가 된다. 따라서 해당 식을 코드로 작성하면 문제를 해결할 수 있다. 코드 fro..

문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 풀이 세로 타일(2 x 1)과 가로 타일(1 x 2) 타일로 n이 입력될 경우 타일을 붙일 수 있는 경우의 수를 구하는 문제이다. n에 따라 발생할 수 있는 각 경우의 수는 크게 3가지 이다. 모두 세로 타일로 구성 되는 경우 모두 가로 타일로 구성 되는 경우 가로, 세로 타일이 혼합되어 구성되는 경우 타일을 붙일 수 있는 경우의 수는 그림 1과 같다. n에 따른 규칙을 찾아보면 n이 증가함에 따라 1, 2, 3, 5, 8, 13로 증가하는 것을 알 수 있다. 이를 식으로 ..

문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀이 문제는 특정 수가 1이 되기 위해서 2, 3으로 나누거나 -1을 하였을 때 최소 횟수로 1을 만드는 방법을 찾는 것이다. 효율적으로 문제를 풀기 위해 메모이제이션(memoization)을 통해 문제를 접근하면 시간초과를 발생시키지 않고 문제를 풀 수 있다. 문제를 푸는 방법은 그림 1과 같다. 그림 1은 10인 경우에 메모이제이션을 통해 값을 찾는 과정이다. 다음과 같은 과정을 반복하여 카운트 값을 누적시켜가는 방식을 사용한다. 각 인덱스는 실제 값을 의미한다. (1 ~ N) 입력된 값과 인덱스를 일치시키기 위해 0번 인덱스를 사용하지 않는다. 입력 값이 1인..

문제 11576번: Base Conversion 타임머신을 개발하는 정이는 오랜 노력 끝에 타임머신을 개발하는데 성공하였다. 미래가 궁금한 정이는 자신이 개발한 타임머신을 이용하여 500년 후의 세계로 여행을 떠나게 되었다. 500년 후의 www.acmicpc.net 문제풀이 이 문제는 A진법을 B 진법으로 변환하는 문제이다. 앞서 다룬 2745 진법 변환, 11005 진법 변환 2 문제 처럼 A 진법을 10진법으로 변환 후에 다시 B 진법으로 변환하도록하여 문제를 풀었다. 앞의 문제들을 잘 풀었다면 이 문제는 더욱 쉽게 풀 수 있다. 코드 if __name__ == "__main__": a, b = map(int, input().split()) m = int(input()) nums = list(map..

문제 11005번: 진법 변환 2 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 �� www.acmicpc.net 문제 풀이 진법 변환 문제에서 10진법의 수를 다시 해당 진법으로 변환하는 문제이다. 10진법의 수를 다른 진법으로 변환하기 위해서는 수가 0이 될 때 까지 나눈 후 각 나머지들을 기록해두면, 변환할 수 있다. 마찬가지로 10 보다 큰 수의 경우 A - Z 로 변환해 주어야 한다. 코드 if __name__ == "__main__": n, b = map(int, input().split()) answer = '' while n: r = n % b ..