1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. 문제 요약 M * N 의 지도가 주어지고, 해당 지도에는 각 칸의 높이가 표시되어 있다. 현재 위치에서 상, 하, 좌, 우 한 곳으로 이동할 수 있으며, 현재 위치보다 낮은 위치로만 이동할 수 있다. 세준이는 0, 0의 위치에서 시작하여 지도의 가장 우측하단까지 이동하는 방법은 모두 몇 가지인가? 2. 접근 방법 0, 0 에서 가능한 모든 경우의 수를 탐색합니다. 재귀로 구현합니다. def solution(y, x): # 목적지 도착 여부 if y == M-1 ..
1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 1. 문제 요약 N * N 의 대나무 숲이 주어지고, 해당 숲에는 대나무의 양이 적혀있다. 판다는 현재 위치에서 상, 하, 좌, 우 한 곳으로 이동할 수 있으며, 이동한 곳의 대나무 양은 이전 위치보다 많아야 한다. 판다가 가장 많이 이동할 수 있는 횟수는 몇번인가? 2. 접근 방법 모든 대나무 숲을 방문합니다. 재귀 함수로 구현합니다. # 재귀함수로 구현 def solution(y, x): move = 0 for dy, dx in [[y-1, x],..
1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 1. 문제 요약 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 빨강, 초록, 파랑으로 집을 칠할 때, 연속되지 않게 칠할 수 있으며, 최소 비용을 구하라. 2. 접근 방법 먼저 가장 완벽한 알고리즘인 완전탐색으로 구현해 보았습니다. N = int(input()) rgb = [list(map(int, input().split())) for _ in range(N)] answer = 1..
11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 1. 문제 요약 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하시오. 2. 접근 방법 숨어있는 규칙을 찾아봅시다. i : 방법 1 -> 1 2 -> 2 3 -> 3 4 -> 5 5 -> 8 6 -> 13 7 -> 21 자세히 살펴보면 규칙을 발견할 수 있습니다. 현재 인덱스의 방법은 이전의 두 인덱스의 방법의 합과 같습니다. 즉, n = (n-1) + (n-2) 가 됩니다. 이는 피보나치 수열의 형태입니다. 이를 토대로 재귀함수를 이용합니다. def solut..
14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 1. 문제 요약 스케줄이 주어지고 해당 스케줄에서 가장 많은 수익을 낼 수 있는 조합을 구하시오 2. 접근 방법 재귀함수를 이용하여 모든 조합을 계산합니다. 그중 가장 많은 수익을 낸 조합을 출력합니다. 3. 파이썬 def solution(index:int, p:int): global P if index == N: P = max(P, p) return elif index < N: solution(index+TP[index][0],p+TP[index][1]) # 일을 하거나 solution(index+1, p) # 하지 않거나 4. 자바 static private void recursive(int in..
19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 1. 문제 요약 N개의 식재료가 주어지고, 해당 식재료를 이용하여 영양성분을 만족하는 최저 비용 조합을 구하라 2. 접근 방법 재귀함수를 이용하여 모든 조합을 구한다. 영양성분을 만족하는 조합들 중 최저 비용을 계산한다. 3. 파이썬 def solution(index:int, used:list): global C, USED if index == N: p, f, s, v, c = 0, 0, 0, 0, 0 for i in used: p += PFSVC[i-1][0]..
2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 1. 문제 요약 재료의 개수 N, 그 재료의 맛 S, B가 주어진다. S는 곱, B는 덧셈으로 맛이 변한다. 재료를 적절하게 조합하여 S와 B의 차가 가장 작은 경우의 맛을 출력하라. 2. 접근 방법 재귀함수를 이용하여 조합을 구해줍니다. 재료를 사용하거나, 사용하지 않거나로 구분하여 진행합니다. 3. 파이썬 from sys import stdin input = stdin.readline def solution(depth:int, used:..
15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1. 문제 요약 주어진 숫자들 중 M개를 뽑아 순열(Permutation)을 생성하는 문제입니다. 출력 시 오름차순으로 정렬하여야 합니다. 2. 접근 방법 순열을 생성하는 대표적인 방법으로 재귀함수를 이용할 수 있습니다. 입력받은 숫자들을 오름차순 정렬 재귀함수를 이용하여 순열 생성 3. 파이썬 from sys import stdin input = stdin.readline def solution(depth: int): if depth == M: prin..
15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 문제 요약 1부터 N까지의 자연수를 사용하여 길이가 M인 수열을 생성하라 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 2. 접근 방법 재귀 함수를 사용합니다. 15650(조합) 과 15651 을 적절히 섞으면 됩니다. 3. 파이썬 from sys import stdin input = stdin.readline def soluti..
