[백준]18429번 근손실

https://www.acmicpc.net/problem/18429

18429번: 근손실

문제

웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 감소하게 된다. 따라서 운동을 하지 않고, 가만히 있다면 매일매일 중량이 감소할 뿐이다.

다행히도 이 대학원생은 N개의 서로 다른 운동 키트를 가지고 있다. 이 대학원생은 하루에 1개씩의 키트를 사용하며, 매일 어떤 키트를 사용할 지는 마음대로 결정할 수 있다. 운동 키트들은 각각의 중량 증가량을 가지고 있으며, 사용할 때마다 즉시 중량이 증가하게 된다. 이 때 몇몇 운동 키트들의 중량 증가량이 같을 수 있으나, 서로 다른 운동 키트로 간주한다. 각각의 운동 키트는 N일 동안 한 번씩만 사용할 수 있다.

대학원생은 운동 기간동안 항상 중량이 500 이상으로 유지가 되도록 N일간의 운동 플랜을 세우고자 한다. 1일차부터 N일차까지의 모든 기간동안, 어떤 시점에서라도 중량이 500보다 작아지지 않도록 해야 한다.

예를 들어 N=3, K=4일 때, 각 운동 키트의 중량 증가량이 다음과 같다고 가정하자.

이 때 1번, 3번, 2번 순서대로 운동 키트를 적용한다고 해보자. 이 경우 운동 1일차에 대학원생은 중량이 3만큼 증가하지만 그와 동시에 하루에 중량이 4만큼 감소하기 때문에, 1일이 지난 이후에 중량은 499가 된다. 따라서 조건을 만족하지 못한다.

반면에 3번, 1번, 2번 순서대로 운동 키트를 적용한다고 해보자. 그러면 1일차부터 운동을 모두 마친 날까지의 모든 시점에 대하여 항상 중량이 500이상이 된다.

N개의 운동 키트에 대한 정보가 주어졌을 때, N일간 하루에 1개씩의 운동 키트를 사용하는 모든 경우 중에서, 운동 기간동안 항상 중량이 500 이상이 되도록 하는 경우의 수를 출력하는 프로그램을 작성하시오.

위 예시에서는 모든 경우 중에서 총 4가지 경우가 조건을 만족한다.

입력

첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 8, 1 ≤ K ≤ 50) 둘째 줄에 각 운동 키트의 중량 증가량 A가 공백을 기준으로 구분되어 주어진다. (1 ≤ A ≤ 50)

출력

N일 동안 N개의 운동 키트를 사용하는 모든 경우 중에서, 운동 기간동안 항상 중량이 500 이상이 되도록 하는 경우의 수를 출력한다.

---

문제가 굉장히 현실감있게 작성되었지만 N의 범위가 1~8 밖에 되지 않아 재귀함수를 사용하면 간단하게 풀 수 있을 것 같았다. 어제 작성한 문제와 유사하면서도 살짝 다른 느낌이였다. 매일 중량이 K 씩 감소하는 와중에 하루에 한개의 운동키트를 활용하여 500 이상을 유지할 수 있는지 판단을 해야하는데 경우의 수 문제라 재귀로 모든 경우의 수를 확인해봐야한다고 생각했다.  임의의 날짜에 임의의 운동키트를 사용할 수 있기 때문에 재귀함수내의 반복문을 활용한다면 문제를 쉽게 풀 수 있을거라 생각했다.

solve()함수를 만들었으며 인자로는 n : 선택한 운동키트 k : 현재 중량 day: 날짜 로 설정하였다. 

종료 조건은 재귀함수 진행 중 중량이 500 밑으로 떨어지는 경우 안되는 경우이기 때문에 바로 return을 하며 이 조건에 걸리지 않고 0~5 를 거쳐 day == 6 까지 진행이 되었다면 성공적으로 배치를 한 경우의 수 이므로 경우의 수를 증가시켜주었다. 

#include <iostream>

using namespace std;
int N, K,ans=0;
int arr[9] = { 0 };
int visited[9] = { 0 };
void solve (int n, int k,int day){
	if (k < 500)
		return;
	else if (day == N) {
		ans++;
		return;
	}
	for (int i = 0; i < N; i++) {
		if (!visited[i]) {
			visited[i] = 1;
			solve(i, k - K +arr[i] , day + 1);
			visited[i] = 0;
		}
	}

}
int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++)
		cin >> arr[i];
	solve(N,500,0);
	printf("%d\n", ans);
}

---

어제 밤에 16974번을 추천받아서 풀려고 하였으나 풀지 못해서 자신감이 조금 떨어졌더니 다른 문제를 추천해주었다. 그래도 이번 문제는 쉽게 풀어서 자신감이 살짝 다시 회복되었다. 16974번도 다시 생각해보아야겠다.