코딩테스트 준비 - 눈덩이굴리기

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

백트래킹DFS

a month ago

13 min read

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

응시 사이트 : BOJ
문제 : 21735.눈덩이굴리기
사용언어 : C#
난이도 : Middle
풀이시간 : 1h over
유형 : 백트래킹 , DFS

문제

눈송이들이 많은 동네인 숙명여대 앞마당에서 눈사람 만들기 대회를 연다. 앞마당의 길이는

$N$ 이고 위치 $1$ 부터 위치 $N$ 까지만 눈이 쌓여있다. 위치 $i$ 에 눈이 $a_i$ 만큼 쌓여있다. 대회 규칙은 해당 앞마당에서 $M$ 초 동안 눈덩이를 굴려 눈사람을 만드는 것이다. 눈덩이의 시작 크기는 $1$ 이다. 눈덩이의 시작 위치는

$0$ 이다.

가장 큰 눈사람을 만들고 싶던 수수는 눈덩이를 굴리는 법을 연구했다. 눈덩이를 굴리는 방법에는 두 가지가 있다. 눈덩이를 굴리거나 던질 때 1초가 소모된다.

눈덩이를 현재 위치 +1칸으로 굴린다. 현재 칸의 위치를

$i$ 라고 하면 눈덩이의 크기는

$a_{i+1}$ 만큼 늘어난다.
눈덩이를 현재 위치 +2칸으로 던진다. 눈덩이가 착지하며 충격을 받아 눈덩이의 크기는 원래의 크기의 반으로 줄어들고 현재 칸의 위치를

$i$ 라고 하면 눈덩이의 크기는 $a_{i+2}$ 만큼 늘어난다. 이 때 소수점은 절사한다. 눈덩이를 던져 크기가

$0$ 이 되어도 눈덩이는 사라지지 않는다.

눈덩이가 앞마당의 끝에 도달한 경우 남은 시간과 관계없이 눈덩이 굴리기는 끝이 난다. 대회 시간 내에 가장 크게 만들 수 있는 눈덩이의 크기를 구하는 프로그램을 작성해보자.

입력

첫째 줄에 공백을 기준으로 앞마당의 길이

$N$ ( $1 \leq N \leq 100$ ), 대회의 시간 $M$ (

$1 \leq M \leq 10$ )이 주어진다.

둘째 줄에 길이가

$N$ 인 수열 $a$ 가 주어진다. (

$1 \leq a_i \leq 1\,000\,000$ )

출력

첫째 줄에 대회 시간 내에 가장 크게 만들 수 있는 눈덩이의 크기를 출력한다.

예제 입력 1

10 5
1 3 4 5 6 7 8 10 12 14

예제 출력 1

문제 풀이 접근

이 문제는 초반 수식도 있고, 방식도 2가지나 존재하고, A_{i+1} 이런 식의 수열 문자도나오고, 겉으로 보기엔 쉽게 움츠러들기 쉬운 문제다.
나도 초기 문제를 이해하고, a_{i+1} 이 현재 + A_{i} 번째 이동한 인덱스의 눈덩이 값을 더하고 하는지 헷갈려서 정의는 GPT를 이해해서 정립한 후에 문제를 풀었다.

문제에서 요구하는건 크게 몇가지 없다. 단, 내가 착각한 점을 기반으로 주의해야할 점을 말하자면,
1. 시작위치는 존재한다. 시작 값도 존재한다. A_{0} = 1 이다.
2. 마지막 수열 부에서 i+2 를 하는 던지는 케이스도 있다. 예외처리 잘하자.
3. 이 눈덩이 굴리기라는 문제는 앞으로만 가기 때문에, for문의 케이스가 필요없다.
4. 문제에서 요구하는 선택지의 방법은 2가지다. 이 두가지 케이스 고려하자.

였다. 이 중 가장 중요한 2가지를 뽑자면 1,3번이었다.
이것들 때문에 더 빨리 풀 수 있는것을 시간 잡아먹었다.

문제에서 예제 입력과 출력대로 문제를 풀어보면 이런 케이스가 선택된다.
10 개의 수열중 5개를 선택해서 내가 만들 수 있는 가장 큰 눈덩이 크기 M 을 출력한다.

여기서 수의 배열을 보면 알다시피, 앞에선 던지는 선택지, 뒤에서는 굴리는 선택지를 선택할수록 큰 눈덩이를 얻을 확률이 높다. 고로 나는 가장 큰 케이스를 바로 찾아냈다.

[ 입력 ]
10 5 1 3 4 5 6 7 8 10 12 14

시작 무게 : 1

[ 로직 ]
1번째 선택지 : 던지기
연산 결과 : (1/2) + 3 => 0.5(소수점 아래 절삭) + 3 = 3
인덱스 : 0 -> 2
뽑은 Cnt : 1

2번째 선택지 : 던지기
연산 결과 : (3/2) + 5 => 1.5(소수점 아래 절삭) + 5 = 6
인덱스 : 2 -> 4
뽑은 Cnt : 2

3번째 선택지 : 던지기
연산 결과 : (6/2) + 7 => 3 + 7 = 10
인덱스 : 4 -> 5
뽑은 Cnt : 3

4번째 선택지 : 굴리기
연산 결과 : 10 + 8 = 18
인덱스 : 5 -> 6
뽑은 Cnt : 4

5번째 선택지 : 18 + 10 = 28
인덱스 : 6 -> 7
뽑은 Cnt : 5

결과 28, 3번의 던지기를 선택 이후 2번의 굴리기를 선택 시 최대 값 M = 28 이 나온다.

보통 순열과 조합을 구하는 방법에서는 for문을 사용해서 만약 수열이 있다면 i < arr.Length 까지 돌려서 찾아내는 풀이 방식이 여럿 존재하는데, 나 또한 i 를 pos 로 두고 뽑히는 수열의 갯수 m 만큼 루프 돌려서 찾는 것으로 방향을 잘못잡아서 시간을 오래잡아먹었다.

이 문제의 경우 계속 한방향으로 나아가는 로직이기 때문에 적절한 함수만 재귀형식으로 짜준다면 반복문이 필요없이 적절한 해답을 찾을 수 있다.

실패한 답안도 같이 첨부하겠다.

실패 작성 코드 (C#) - Loop문 사용하여 실패

using System;
using System.Collections.Generic;
using System.Text;

namespace Test
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Solution solution = new Solution();
            solution.solve();
        }
    }

    public class Solution
    {
        public int _n;
        public int _m;
        public int[] _arr;
        public int[] _per;

        public float _ret = 0;

        public void solve()
        {
            _ret = float.MinValue;
            string[] _in = Console.ReadLine().Split(' ');
            _n = int.Parse(_in[0].ToString());
            _m = int.Parse(_in[1].ToString());

            _in = Console.ReadLine().Split(' ');
            _arr = new int[_in.Length];

            for (int i = 0; i < _in.Length; ++i)
                _arr[i] = int.Parse(_in[i].ToString());

            dfs(0, 0,0f, false);

            Console.Write(_ret);
        }

        public void dfs(int cnt, int pos,float calc, bool isThrow)
        {
            if (cnt >= _m || pos > _n)
            {
                if (_ret < calc)
                    _ret = calc;
            }
            else
            {
                for (int i = pos; i < _m; ++i)
                {
                    // 1번으로 수행했을 때, 
                    dfs(cnt + 1, i+1 ,calc + _arr[i], false);

                    // 2번으로 수행했을 때,
                    float calcThrow = calc * 0.5f;
                    int valBasedLength = ((i + 1) >= _arr.Length) == true ? 0 : _arr[i+1];
                    dfs(cnt + 1, i+2, calcThrow + valBasedLength, true);
                }
            }
        }

        public int GetVal(char a)
        {
            if (a == 'I')
                return 1;
            if (a == 'V')
                return 5;
            if (a == 'X')
                return 10;
            if (a == 'L')
                return 50;

            return 0;
        }
    }
}

작성 코드 (C#) - 성공

using System;
using System.Collections.Generic;
using System.Text;

/////*
//// * Difficulty : Middle
//// * URL : https://www.acmicpc.net/problem/21735
////  * Time : 1h over
//// */

namespace Test
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Solution solution = new Solution();
            solution.solve();
        }
    }

    public class Solution
    {
        public int _n;
        public int _m;
        public int[] _arr;
        public int[] _per;

        public float _ret = 0;

        public void solve()
        {
            _ret = float.MinValue;
            string[] _in = Console.ReadLine().Split(' ');
            _n = int.Parse(_in[0].ToString());
            _m = int.Parse(_in[1].ToString());

            _in = Console.ReadLine().Split(' ');
            _arr = new int[_in.Length];

            for (int i = 0; i < _in.Length; ++i)
                _arr[i] = int.Parse(_in[i].ToString());

            dfs(0, 0, 1f, false);

            Console.Write(_ret);
        }

        public void dfs(int cnt, int pos, float calc, bool isThrow)
        {
            if (cnt >= _m || pos >= _n)
            {
                if (_ret < calc)
                    _ret = calc;
            }
            else
            {
                    // 1번으로 수행했을 때, 
                    dfs(cnt + 1, pos + 1, calc + _arr[pos], false);

                    // 2번으로 수행했을 때,
                    float calcThrow = calc * 0.5f;
                    int valBasedLength = ((pos + 1) >= _arr.Length) == true ? 0 : _arr[pos + 1];
                    dfs(cnt + 1, pos + 2,  (float)Math.Floor(calcThrow + valBasedLength), true);
            }
        }
    }
}

코드 결과