[알고리즘/프로그래머스] N으로 표현 - C++

오늘은 동적 계획법(일명 DP)을 사용해볼 예정이다.

'N으로 표현'이란 문제인데 문제만 보면 어려워 보인다.

차근차근 해결해나가자.

*본인은 C++로 코딩할 예정이다.

---

1. 문제

아래와 같이 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 함수를 작성하세요.

 

출저 - 프로그래머스

2. 사고 - 동적 계획법(DP)

1. N을 사용한 횟수에 따라 만들 수 있는 수들이 생긴다(정해진다).

2. 직접 계산해보며 N에 따른 사용횟수를 일반화 해본다. > 3을 한번 사용하면 3, 두번 사용하면 33과 사칙연산 값인 6, 0, 9, 1을 산출 할 수 있다.

3. 일반화한 공식을 코딩으로 적용해본다.

4. 동적 계획법으로 탐색범위를 확실히 좁혀야 하는데에 집중하여야 한다.

3. 코딩

#include <iostream>
#include <unordered_set>
#define MAXN 8
using namespace std;

int solution(int N, int number) {
	int answer = -1, std = 0;
	unordered_set<int> us[MAXN];
	for (int i = 0; i < MAXN; i++) {
		std = 10 * std + 1;
		us[i].insert(std * N);
	}
	for (int i = 1; i < MAXN; i++) {
		for (int j = 0; j < i; j++) {
			for (auto& op1 : us[j]) {
				for (auto& op2 : us[i - j - 1]) {
					us[i].insert(op1 + op2);
					us[i].insert(op1 - op2);
					us[i].insert(op1 * op2);
					if (op2 != 0) {
						us[i].insert(op1 / op2);
					}
				}
			}
		}
		if (us[i].count(number) > 0) {
			answer = i + 1;
			break;
		}
	}
	return answer;
}

int main(void) {
	int N, number;
	N = 3;
	number = 12;
	cout << solution(N, number) << endl;

	return 0;
}

- N = 3, number = 12

 

- 과정1 : us[0] = 3, us[1] = 33, us[2] = 333, us[3] = 3333, us[4] = 33333, us[5] = 333333, us[6] = 3333333, us[7] = 33333333

- 과정2 : us[1] = {33, 6, 0, 9, 1}

- 과정3 : us[2] = {333, 4, 2, 3...12...}

- 과정4 : us[2] {...12...} 존재 확인, answer = i + 1

- answer = 3

- 3*3 + 3 = 12

 

- 결과 : 3

 

4. 알게된 것

다이나믹 프로그래밍이란?

문제의 답을 확인하기 위해서 확인하는 범위를 줄여가며 동적으로 결정해나가는 방식

 

동적 계획법을 사용하기 위해선 문제에 대한 충분한 이해를 필요로 한다.

문제를 잘 읽고 확인 범위를 줄여나가기 위한 설계를 철저히 진행해야 한다.

 

 

---

난이도도 다이나믹하다.