MingyuPark

문제 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 아이디어 재귀 호출로 실행하면 시간 초과가 발생한다. 이 경우는 DP를 이용해서 쉽게 해결할 수 있다. a, b, c 3개의 변수를 받기 때문에 3차원 배열을 생성한다. (a, b, c) 중 음수가 있는 경우 1을 반환하고, 모두 20보다 큰 경우 w(20, 20, 20)을 반환하도록 한다. 이 때 재귀적으로 호출하면 w(20, 20, 20)를 구하기 위한 모든 과정을 반복해야 한다. w(a, ..

문제 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 아이디어 주어진 N개의 자연수의 S번째부터 E번째까지의 수가 팰린드롬을 이루는지의 여부를 나타내는 2차원 배열을 이용한다. 즉, N×N의 배열을 초기화한 후, S번째부터 E번째까지의 수가 팰린드롬을 이루는 경우는 배열의 (S, E)번째 성분을 1로, 팰린드롬을 이루지 않는 경우는 0으로 둔다. 이 문제는 크게 3가지로 나눌 수 있다. - 주어진 숫자열의 길이가 1인 경우(즉, S = E인 경우) - 주어진 숫자열의 길이가 2인 경..

문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 아이디어 N킬로그램에서 필요한 봉지의 수를 f(N)이라고 하자. 이 경우 봉지를 하나 추가하는 경우는 3kg 봉지를 하나 추가하는 경우와 5kg 봉지를 하나 추가하는 경우 둘 중 하나이다. 즉, f(N) = f(N-3) + 1이거나 f(N) = f(N-5) + 1이 될 수 있다. f(N-3)과 f(N-5)의 대소관계를 비교해야 한다. 봉지 수가 가장 적은 경우를 구해야 하기 때문에 f(N-3)과 f(N..

문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 아이디어 P(N) = P(N-5) + P(N-1)로 나타낼 수 있다. P(N)의 값을 저장해놓고 사용하면 메모리를 절약할 수 있다. 이 때, P(5)까지는 직접 입력해주고 P(6)부터는 점화식으로 표현할 수 있다. Solution t = int(input()) cache = [0 for _ in range(101)] cache[1] = 1 cache[2] = 1 cache[3] = 1 cache[..

문제 11726번: 2×n 타일링 (acmicpc.net) 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 아이디어 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 f(n)이라고 하면 이를 점화식으로 표현할 수 있다. f(1) = 1, f(2) = 2이다. n이 3 이상인 경우 f(n) = f(n-1) + f(n-2)로 표현할 수 있다. f(4) = f(3) + f(2) = {f(2) + f(1)} + f(2) 와 같은 방식으로 계산이 진행되기 때문에 recursive call을 이용하면 메모리가 낭비될 수 있다..

문제 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 아이디어 동쪽(M개)의 사이트에서 서쪽(N개)의 사이트를 선택하는 문제로 간단한 조합 문제이다. 조합을 이용하면 쉽게 해결할 수 있다. 아이디어 자체는 어렵지 않았고 조합을 구현할 때 factorial, combination을 직접 구현해보고, 모듈을 이용해서도 풀어봤다. Solution 1. factorial을 직접 구현 def factorial(n) : num = 1 for i in ra..