다시푸는 코딩 테스트 준비 일지
문제
웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 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 이상이 되도록 하는 경우의 수를 출력한다.
예제 입력 1 복사
3 4
3 7 5
예제 출력 1 복사
4
문제 풀이 접근
이 문제는, 2가지 유형이 섞인 문제라고 생각한다.
1. 백트래킹을 먼저하여 순서를 구해야하고,
2. 그 순서를 가지고 완전탐색을 하여야 풀 수 있다.
먼저 백트래킹이란 내가 할 수 있는 여러가지 경우의 수를 하나씩 수행하는 것을 말한다.
만약 A B C 가 있을때 내가 A 를 방문하고 나머지는 B C 를 선택할 수 있다. 그다음에 B 를 선택하면 순서는 A - B 여서 그다음에 선택할 수 있는 문자는 C 다 그러면 가장 먼저 A - B - C 를 순회하게 되고, 이게 내가 찾는 답이 아니라면, 다시 A 선택한 시점으로 돌아온다.
아까는 B C 중에 B를 골랐지만, 이번에는 C 를 고르면 A - C - B 순서로 방문함을 알 수 있다.
이렇게 내가 할 수 있는 선택지를 가지치기를 통하여 유망한 답중 정답을 골라내는 방법이다.
원리를 보면 DFS, BFS와 상당히 유사하다고 생각하나, 백트래킹이 쉽게 풀 수 있는 문제들이 따로 있기 때문에 백트래킹은 연습이 좀 필요할 것으로 보인다.
다시 문제로 돌아와서, 1(5), 2(7), 3(3) 으로 키트와 중량 증가량이 쌍으로 있다.
이것또한 순열로 풀면
1 - 2 - 3
1 - 3 - 2
2 - 1 - 3
2 - 3 - 1
3 - 1 - 2
3 - 2- 1
이렇게 되는데 사용 순서에 따라 내가 500을 계속 유지할 수 도 있고, 500을 유지 못할 수도 있다.
여기서 하루에 K 만큼 감소하니까 나는 _nowWeight 라는 변수로 현재 내가 어디까지 들 수 있는지 공식을 세웠다 .
nowWeight = nowWeight - ( K ) + Kitval 을 매일 계산하다보면 내가 500을 넘는지 알 수 있다.
그렇게 모든 케이스가 500을 넘으면 _ret 을 하나 증감하고 모두 순회했다면 ret 을 출력하면 끝나는 문제다.
작성 코드 (C#)
using System;
using System.Collections;
using System.Collections.Generic;
using static CodingTestProj.Program;
/*
* Difficulty : Middle
* URL : https://www.acmicpc.net/problem/18429
* Time :
*/
//mobitel
namespace CodingTestProj
{
internal class Program
{
static void Main(string[] args)
{
var ss = new Solution();
ss.solve();
}
}
public class Solution
{
public int _n;
public int _k;
public int _declineProtain;
public bool[] _isSelected;
public int[] _numbers;
public int _ret;
public int _permuteCnt;
public int _nowWeight;
public int _dic_index;
public Dictionary<int, int> _dicKitVal = new Dictionary<int, int>();
public List<KeyValuePair<int, List<int>>> _listPermute = new List<KeyValuePair<int, List<int>>>();
public void solve()
{
Init();
string[] input = Console.ReadLine().Split(' ');
_n = Int32.Parse(input[0]);
_k = Int32.Parse(input[1]);
_isSelected = new bool[_n];
_numbers = new int[_n];
for (int i = 0; i < _n; ++i)
_numbers[i] = i + 1;
input = Console.ReadLine().Split(' ');
for (int i = 1; i <= _n; ++i)
_dicKitVal.Add(i, Int32.Parse(input[i - 1]));
int[] arr = new int[_n];
Permutation(0, 0, ref arr);
MainSolution();
Print();
}
public void Init()
{
_n = 0;
_k = 0;
_declineProtain = 0;
_dic_index = 0;
_nowWeight = 500;
}
public void Permutation(int _depth, int _pos, ref int[] arr)
{
if (_depth == (_n))
{
List<int> _mList = new List<int>();
_mList.AddRange(arr);
_listPermute.Add(new KeyValuePair<int, List<int>>(_dic_index, _mList));
//for (int i = 0; i < _mList.Count; ++i)
// Console.Write(_mList[i] + " ");
//Console.WriteLine();
++_dic_index;
}
else
{
for (int i = 0; i < _numbers.Length; ++i)
{
if (_isSelected[i] == false)
{
_isSelected[i] = true;
arr[_depth] = _numbers[i];
Permutation(_depth + 1, _pos, ref arr);
_isSelected[i] = false;
}
}
}
}
public void MainSolution()
{
for (int i = 0; i < _listPermute.Count; ++i)
{
var val = _listPermute.Find(rhs => rhs.Key == i).Value;
if (val == null) continue;
_nowWeight = 500;
bool isFail = false;
for (int j = 0; j < val.Count; ++j)
{
var kitNumb = val[j];
var kitVal = _dicKitVal[kitNumb];
_nowWeight = _nowWeight - (_k) + kitVal;
if (_nowWeight < 500)
{
isFail = true;
break;
}
}
if (isFail) continue;
++_ret;
}
}
public void Print()
{
Console.WriteLine(_ret);
}
}
}
코드 결과
어째서 인지 이미지가 안붙여진다.
고쳐지면 첨부예정