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..
12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1. 문제 요약 물품의 수 N, 버틸 수 있는 무게 K, 각 물건의 무게 W, 물건의 가치 V가 주어집니다. 물건들을 가장 많이 가져갈 수 있는 조합을 구하시오. 2. 접근 방법 먼저 완전탐색으로 모든 경우의 수를 다 때려 넣어봅니다. def solution(idx, w, v): global answer if w > K: return if idx == N: answer = max(answer, v)..
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]..
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..
15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 문제 요약 1부터 N까지의 숫자들 중 M개를 뽑아 수열을 생성하라. 같은 수를 여러 번 골라도 된다. 2. 접근 방법 대표적인 방법으로 재귀함수를 이용할 수 있습니다. 3. 파이썬 from sys import stdin input = stdin.readline def solution(depth: int): if depth == M: # print(*arr) print(' '.join(map(str, arr))) # 위 방식보다 좀 더 효율적입니다. retu..
14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 1. 문제 요약 1부터 N까지의 숫자들 중 M개를 뽑아 조합(Combination)을 만드는 문제입니다. 2. 접근 방법 조합을 생성하는 대표적인 방법으로 재귀함수를 이용할 수 있습니다. 3. 파이썬 from sys import stdin input = stdin.readline def solution(start: int, depth: int): if depth == M: print(*arr) return for i in range(start, ..
