[프로그래머스 Level 3] [동적계획법] N으로 표현 (C++)

안녕하세요! 코딩하는 경제학도 쏘코입니다.

이번에는 새로운 동적계획법(DP) 문제로 돌아왔습니다.

DP는 과거의 해를 활용하는 방식의 알고리즘입니다.

사실 다이나믹..하지 않은데, 왜 다이나믹이라는 이름이 붙었는 지는 모르겠습니다 ㅋㅋㅋㅋㅋㅋ

분할정복의 일종이라고 보시면 될 것 같습니다. 어떤 교수님은 기억하며 풀기 등으로 다르게 표현하셨더군요.

그렇다면 신기한 동적계획법 문제풀이로 가보도록 하겠습니다!

출처 : 프로그래머스 코딩테스트 연습 고득점 KIT, programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - N으로 표현

programmers.co.kr

0. 문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.

이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

0.0. 제한사항

N은 1 이상 9 이하입니다.
number는 1 이상 32,000 이하입니다.
수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
최솟값이 8보다 크면 -1을 return 합니다.

0.1. 입출력 예

N	number	return
5	12	4
2	11	3

0.2. 입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

1. 풀이 과정

DP의 개념을 파악하는 것이 가장 중요합니다.

N의 사용 횟수가 늘어가는 것을 사용 횟수가 적은 경우의 수들을 이용해 구할 수 있습니다.

먼저 N이 1개인 경우는 당연히 경우의 수가 N뿐입니다.

N이 2개인 경우는 NN과 N+N, N-N, N*N, N/N이 가능합니다.

N이 3개인 경우는 NNN과 (NN+N, NN-N, NN*N, NN/N), ((N+N)+N), (N+N)-N, (N+N)*N. (N+N)/N), ((N-N)+N), (N-N)-N, (N-N)*N. (N-N)/N), ((N*N)+N), (N*N)-N, (N*N)*N. (N*N)/N), ((N/N)+N), (N/N)-N, (N/N)*N. (N/N)/N)이 가능합니다. 이것은 다르게 말하면 s[2]는 NNN과 s[1]과 s[0]의 사칙연산, s[0]과 s[1]의 사칙연산의 합이라고 말할 수 있습니다.

반복해서 s[3]은 NNNN과 s[2]와 s[0], s[1]과 s[1], s[0]과 s[2]의 사칙연산의 합입니다.

이걸 s[7] (N을 8개 쓴 것)까지 반복하면 구할 수 있습니다.

알고리즘을 생각해냈으니 구현은 그렇게 어렵지 않습니다.

먼저 answer의 기본값을 -1로 설정합니다. i가 7을 넘어가면 -1을 출력하라고 했기 때문입니다.

그리고 연산 과정에서 중복값이 발생할 수 있기 때문에 자료구조로는 set을 사용합니다.

정렬은 딱히 필요 없고 어짜피 전수조사를 해야 하기 때문에 unordered_set를 사용했습니다.

먼저 각 항목에 N을 연달아 쓴 것들을 set에 넣어줍니다. for문과 int변수 하나를 이용해 간단하게 만들 수 있습니다.

그 다음엔 사칙연산한 것들을 set에 넣어줍니다.

s[3]은 N이 연달아 4개 있는 것과 s[0]과 s[2]의 조합, s[1]과 s[1]의 조합, s[2]와 s[0]의 조합의 합집합입니다.

여기서 이중for문을 사용할 때 s[j]와 s[N의 개수-j-1]을 사칙연산으로 조합한 것들을 s[i]에 넣어줘야 합니다.

그렇기에 for문 안의 조건이 첫 for문에서는 i는 1부터 7까지, j는 0부터 i-1까지 돌도록 만들었습니다.

i랑 j는 같을 수 없고(s[i]을 구할 때 부분집합의 인덱스는 최대 i-1이니까요! s[3]을 예로 들면 부분집합의 인덱스는 (0,2),(1,1),(2,0)의 조합입니다), s[7]까지만 구하면 되기 때문에 직접 사칙연산할 set은 s[6]까지니까 j의 경우 j<i, i 미만(i는 최대 7)까지만 돌리면 됩니다.

그리고 :을 사용한 범위 기반 반복문을 통해 간단하게 s의 원소들을 a와 b로 가져와서 사칙연산에 사용했습니다.

이제 사칙연산한 내용을 그대로 set에 넣으면 됩니다. 다만 여기서 신경써야 할 부분은 b에 0이 들어갈 가능성이 있기 때문에 그 부분을 제거해야합니다. 그렇지 않으면 아래와 같은 부동소수점 오류와 마주치게 됩니다.

set을 꽉 채웠으면 이제 number가 set들 안에 들어가 있는지 확인합니다. s[0]부터 s[7]까지 순서대로 확인합니다. 발견하면 i+1을 answer로 반환합니다. 왜냐구요? 우리는 N이 1개일 때 i를 0이라고 했기 때문에 i+1을 반환하면 됩니다. i=7까지 발견하지 못하면 그대로 for문을 빠져나와서 answer의 기본값 -1을 반환하도록 했습니다. 그럼 끝!

2. 소스 코드

#include <string>
#include <unordered_set>

using namespace std;

int solution(int N, int number) {
    int answer = -1; // 최솟값이 8보다 크면 -1을 return
    unordered_set<int> s[8]; // 정렬할 필요 X, 중복제거는 필요 - unordered_set 사용
    
    int sum = 0;
    for(int i = 0; i < 8; ++i){ // 각 항목에다가 N, NN, NNN... 넣어줌
        sum = 10*sum + N;
        s[i].insert(sum);
    }
    
    for (int i = 1; i < 8; ++i){
        for(int j = 0; j < i; ++j){
            for(int a : s[j]){
                for(int b : s[i-j-1]){
                    s[i].insert(a+b);
                    s[i].insert(a-b);
                    s[i].insert(a*b);
                    if(b != 0)
                        s[i].insert(a/b);
                }
            }
        }
    }
    
    // set을 채웠으니 number가 set에 들어가 있는지 여부만 확인하면 된다!
    for(int i = 0; i < 8; ++i){
        if(s[i].find(number) != s[i].end()){
            answer = i + 1;
            break;
        }  
    }
        
    
    return answer;
}

3. 후기

DP가 뭔지도 모르는 상태에서 DP문제를 풀기란 굉장히 어려웠습니다. 문제를 딱 보자마자 이걸 어케풀어 소리가 절로 나왔으니까요. DP의 개념을 어느 정도 파악하고 약간의 검색을 통해 힌트를 얻어 해결했습니다. 그래서 완벽하게 DP문제에 익숙해졌다고 보기는 힘들겠네요.

그래도 다음 문제는 힌트 없이 풀어보도록 노력해보도록 하겠습니다. 차츰 익숙해지겠죠?!

저작자표시

[프로그래머스 Level 3] [동적계획법] N으로 표현 (C++)