https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net 풀이 백트래킹 문제라고 분류가 되어있었지만, 딱히 고려하고 풀진 않았다. 조건 중에 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 8, 1 ≤ K ≤ 50) 둘째 줄에 각 운동 키트의 중량 증가량 A가 공백을 기준으로 구분되어 주어진다. (1 ≤ A ≤ 50) 가 있어서 일일이 다 확인해도 된다고 생각하여 하나씩 다 순회해보기로 하였다. 처음 생각한 풀..
알고리즘/BOJ
https://www.acmicpc.net/problem/17213 17213번: 과일 서리 민건이네 과일 농장은 N가지 종류의 과일을 재배하는 중이다. 평소 민건이에게 앙심을 품고 있던 지환이는 민건이를 골탕 먹이기 위하여 민건이네 과일 농장에서 과일들을 훔치기로 다짐했다. www.acmicpc.net 풀이 문제를 딱 보자마자 중복조합이 떠올라 중복조합로 풀어버렸다. nHr과 같은 기호로 표시하는게 중복조합인데, 그 당시 외우는 걸 안 좋아하고, 중복조합이라는 이름 자체도 나만의 풀이로 해석했었는데 그 방식을 소개하고자 한다. 먼저 중복조합이란? n개의 서로 다른 원소 중에서 중복을 허락해 r개를 뽑는 경우의 수 이다. 나는 이 중복조합을 나만의 방식으로 해석했었는데 알아두면 좋은 해석이다. 그 당시 ..
https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 풀이 먼저 문제를 읽고 알약이 2개였을 때와 3개였을 때 그림을 그려보니 알약이 3개일 때 알약 하나 먹고 반 개를 먹었을 때 알약 2개의 상황과 같다는 것을 인지하고, 이전의 결과를 사용할 수 있구나 먼저 생각하게 되었다. 그러던 중 예제 입력 1,2,3,4에 대해 1,2,5,14가 나오는 것을 보고 이전에 공부했었던 Catalan Number가 생각났었다. 카탈란 수를 나는 길찾기의 한 유형이라고 공부했었는데..
