코딩테스트 준비 - 로마 숫자 만들기

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

백트래킹DFS

a month ago

7 min read

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

응시 사이트 : BOJ
문제 : 16922.로마숫자만들기
사용언어 : C#
난이도 : Middle
풀이시간 : 1h over
유형 : 백트래킹 , DFS

문제

로마 숫자에서는 수를 나타내기 위해서 I, V, X, L을 사용한다. 각 문자는 1, 5, 10, 50을 의미하고, 이 문제에서 다른 문자는 사용하지 않는다.

하나 또는 그 이상의 문자를 이용해서 수를 나타낼 수 있다. 문자열이 나타내는 값은, 각 문자가 의미하는 수를 모두 합한 값이다. 예를 들어, XXXV는 35, IXI는 12를 의미한다.

실제 로마 숫자에서는 문자의 순서가 중요하지만, 이 문제에서는 순서는 신경쓰지 않는다. 예를 들어, 실제 로마 숫자에서 IX는 9를 의미하지만, 이 문제에서는 11을 의미한다.

로마 숫자를 N개 사용해서 만들 수 있는 서로 다른 수의 개수를 구해보자.

입력

첫째 줄에 사용할 수 있는 문자의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 로마 숫자 N개를 사용해서 만들 수 있는 서로 다른 수의 개수를 출력한다.

예제 입력 1 복사

예제 출력 1 복사

I, V, X, L을 만들 수 있다.

예제 입력 2 복사

예제 출력 2 복사

2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다.

예제 입력 3 복사

예제 출력 3 복사

문제 풀이 접근

이 문제의 풀이 방식 자체는 이전에 했던 N과 M 시리즈와 상당히 유사하다.
단지 I V X L 등의 문자를 숫자로 변경해 나올 수 있는 숫자의 종류를 돌려주는 문제다.

이 문제를 더 빠르게 풀기 위해, 탐색 속도를 올리기위해 해쉬테이블 기반의 유니크한 값을 가지는 HashSet을 사용했으나, 4^20 의 가짓수를 2초 내에 패스하는 것에 무리가 있어 시간초과로 패스하지 못했다.

이 방식을 수정하기 위해, HashSet대신 Count 를 증가하면서 해보아도 시간 초과가 나왔고, bool 배열로 카운트를 해도 시간초과가 나왔다.

해결법은 아래와 같다.
문제를 보면 IXVL로 4가지의 선택지가 있고, 최대 20번 뽑을 수 있다.
고로 아까 위에 적어둔 4^20번 호출될 수 있고, 이는 상당히 무거운 호출 수다.
15번만 뽑아도 대략 5~6초가 걸렸었다.

그렇기 때문에, 모든 케이스에서 4번 뽑는 선택지를 최대한 줄여주도록 해야한다.
4가지 문자에서 2가지를 뽑는다면 이렇게된다.
II IV IX IL
VI VV VX VL
XI XV XX XL
LI LX LV LL
이 식에서 잘보면 (1,2) 와 (2,1)은 IV , VI => 값 : 6 으로 같다. 고로, II VV XX LL 와 같이 볼드체인 숫자를 기준으로 대칭되는 수는 한번만 뽑아도 된다.
왜? 문제에서 숫자의 가짓수를 반환하길 원하니 한번만 뽑으면된다.
이렇게 하면
II IV IX IL
VI VV VX VL
XI XV XX XL
~~LI LX LV~~ LL
이렇게된다. 이를 코드로 나타내면 최적화가 된다.
처음 I 를 뽑을때는 I 부터 V X L 을 다뽑아도된다.
그 후 V로 넘어올 때는 VI를 찾을 필요가 없기 때문에, V의 배열상 위치인 1위치부터 시작하여 순회하면 된다 ( 배열 시작은 0위치 부터 시작함.)

값을 저장하기 위한 인덱스를 계속해서 파라미터로 넘겨주고, 2장 뽑은 경우 내가 만들어 놓은 bool 배열을 true로 변경하거나, false 를 true 로 바꾸는 상황에만 count를 올려주면 뽑을 수 있는 최대한의 갯수를 알 수 있다.

작성 코드 (C#)

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

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

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

    public class Solution
    {
        public const int maxValues = 50;
        public const int max = 20;
        public int _n;
        public int _m;
        public char[] _arr;
        public char[] _per;
        public bool[] _checkCnt;

        public int _ret = 0;

        public void solve()

        {
            _checkCnt = new bool[(maxValues * max) + 1];
            string _in = Console.ReadLine();
            _n = 4;
            _m = int.Parse(_in.ToString());

            _arr = new char[4];
            _arr[0] = 'I';
            _arr[1] = 'V';
            _arr[2] = 'X';
            _arr[3] = 'L';

            _per = new char[max];

            dfs(0, 0, 0);

            Console.Write(_ret);
        }

        public void dfs(int cnt, int pos, int calc)
        {
            if (cnt >= _m)
            {
                if (_checkCnt[calc] == false)
                {
                    _checkCnt[calc] = true;
                    ++_ret;
                }
            }
            else
            {

                for (int i = pos; i < _n; ++i)
                {
                    dfs(cnt + 1, i, calc + GetVal(_arr[i]));
                }
            }
        }

        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;
        }
    }
}

코드 결과