코딩테스트 준비 - 백설 공주와 일곱 난쟁이

혼자서 다시푸는 코딩테스트 준비 일지 - 34

브루트포스조합

3 months ago

5 min read

다시푸는 코딩 테스트 준비 일지

응시 사이트 : BOJ
문제 : 3040.백설 공주와 일곱 난쟁이
사용언어 : C#
난이도 : 중하
풀이시간 : 2h over
유형 : 브루트포스, 조합

문제

매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다.

어느 날 광산에서 아홉 난쟁이가 돌아왔다. (왜 그리고 어떻게 아홉 난쟁이가 돌아왔는지는 아무도 모른다) 아홉 난쟁이는 각각 자신이 백설공주의 일곱 난쟁이라고 우기고 있다.

백설공주는 이런 일이 생길 것을 대비해서, 난쟁이가 쓰고 다니는 모자에 100보다 작은 양의 정수를 적어 놓았다. 사실 백설 공주는 공주가 되기 전에 매우 유명한 수학자였다. 따라서, 일곱 난쟁이의 모자에 쓰여 있는 숫자의 합이 100이 되도록 적어 놓았다.

아홉 난쟁이의 모자에 쓰여 있는 수가 주어졌을 때, 일곱 난쟁이를 찾는 프로그램을 작성하시오. (아홉 개의 수 중 합이 100이 되는 일곱 개의 수를 찾으시오)

입력

총 아홉개 줄에 1보다 크거나 같고 99보다 작거나 같은 자연수가 주어진다. 모든 숫자는 서로 다르다. 또, 항상 답이 유일한 경우만 입력으로 주어진다.

출력

일곱 난쟁이가 쓴 모자에 쓰여 있는 수를 한 줄에 하나씩 출력한다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

문제 풀이 접근

이 문제를 풀면서 2가지 접근법을 생각했다.
1. for문을 7개 돌려서 100에 한하는 방법을 찾는 방법
2. 조합을 이용해서 순차적으로 탐색하면서 찾아내는 방법

문제를 푸는데 있어서 순열과 조합은 나중에도 필요하기 때문에, 감을 다시 새기는 느낌으로 구현해보았는데, 까먹어서 원활히 풀지는 못했다.

조합 알고리즘은 조합 배열 Arr에서 r개를 뽑아 c라는 조합 배열을 만드는 것인데,
(조합에 대한 개념은 추후에 이미지로 다시 포스팅 할 예정)

결론적으로 Arr 9개에서 r 7개를 뽑고 이 C의 값을 합산하여 100을 이룰 때 조합을 출력하면 쉽게 풀 수 있다.

정답 작성 코드 (C#)

using System;
using System.CodeDom;
using System.Collections.Generic;
using System.ComponentModel;
using System.ComponentModel.Design;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Security.AccessControl;
using System.Security.Authentication;
using System.Security.Cryptography;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Web;
using System.Xml.Linq;
using static CodingTestProj.Program;

/*
 * Difficulty : Middle
 * URL : https://www.acmicpc.net/problem/3040
 * Time : 2h over
 */


namespace CodingTestProj
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Solution solution = new Solution();
            solution.solve();
        }
    }
    public class Solution
    {
        int _count = 9;
        int _target = 100;

        bool _isPass = false;

        public void solve()
        {
            int[] arr = new int[9];

            for (int i = 0; i < _count; ++i)
            {
                int val = Int32.Parse(Console.ReadLine());
                arr[i] = val;
            }
            
            int[] conbination = new int[7];
            Combination(arr, conbination, 7, 0, 0);
        }

        public void Combination(int[] arr, int[] combination, int r, int pos, int depth)
        {
            if(r == 0)
            {
                int val = 0;

                for(int i =0; i < combination.Length; ++i)
                    val += combination[i];

                if(val == 100)
                {
                    for (int i = 0; i < combination.Length; ++i)
                        Console.WriteLine(combination[i]);
                }
            }
            else if (depth == arr.Length)
            {
                return;
            }
            else
            {
                combination[pos] = arr[depth];

                Combination(arr, combination, r - 1, pos + 1, depth + 1);
                Combination(arr, combination, r  , pos, depth + 1);
            }
        }
    }
}