CEO

문제 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 ..

문제 2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 문제 풀이 진법 변환을 하기 위해선 각 자리에 해당 하는 위치에 따라 위치 값을 제곱해주면 된다. 예를 들어 예시와 같은 ZZZZZ인 경우는 (35 * 36 ^ 4) + (35 * 36 ^ 3) + (35 * 36 ^ 2) + (35 * 36 ^ 1) + (35 * 36 ^ 0)의 값이 10진법으로 변환된 값이다. 다른 문제와 달리 알파벳 A - Z도 같이 입력되므로 이를 구분하여 처리하여야 한다. isdigit()를 활용하여 문자, 숫자를 구분한다. 문자인..

문제 2089번: -2진수 -2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 110 www.acmicpc.net 문제 풀이 처음에는 어떻게 구해야 하나 고민을 했는데, 가만히 생각해 보면 2진수를 계산하듯이 동일하게 계산하면 된다. 문제의 예시인 -13의 경우 다음과 같이 계산 된다. 코드 if __name__ == '__main__': num = int(input()) binary = '' if not num: print('0') exit() else: while nu..

문제 17103번: 골드바흐 파티션 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 문제 풀이 골드바흐의 추측은 두 소수의 차가 가장 큰 것을 반환하는 것이므로 최초에 만족하는 소수를 찾은 경우 더 이상 진행하지 않고 중지하면 된다. 이와 달리 골드 바흐 파티션은 순서가 다른 소수 예를 들어 6인 경우 (1, 5) (5, 1)은 동일하게 취급하고 짝수가 주어 질 때 만족하는 개수를 반환하는 문제이다. from sys import stdin def is_prime(n): nums = [True] * n for i in range(2, int(n..