N으로 표현 (Level 3)
문제
코딩테스트 연습 - N으로 표현
programmers.co.kr
접근법
이 문제에서 구해야 하는 값은 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현할 수 있는 방법 중 N 사용 횟수의 최솟값이다. 이 문제를 풀기 위해서는 집합의 개념과 동적 계획법을 활용할 것이다. 우리는 최악의 경우 N을 8번 써서 만들 수 있는 수 들도 계산해야 하는데, N을 1회 써서 만들 수 있는 수들의 집합을 활용해서 2회 써서 만들 수 있는 수들을 구하고, N을 2회 써서 만들 수 있는 수들의 집합과, 1회 써서 만들 수 있는 수들의 집합을 활용해서 3회 써서 만들 수 있는 집합을 구할 것이다. 이렇게 4회, 5회... 8회까지 계산을 할 것이기 때문에 이는 동적 계획법 중에서도 바텀업(Bottom - Up) 방식이 된다.
N이 5인 경우를 예를 들어서 설명하겠다. 5을 1회 사용해서 만들 수 있는 수들과 2회, 3회... n회 (n의 최댓값은 8) 사용해서 만들 수 있는 수들의 집합을 생각해보자.
Set[1] : { ... }
Set[2] : { ... }
Set[3] : { ... }
Set[4] : { ... }
Set[5] : { ... }
Set[6] : { ... }
Set[7] : { ... }
Set[8] : { ... }5를 1회 사용하는 Set[1]에는 어떤 수가 들어갈 수 있을까? 5를 한번 쓰기 때문에 만들 수 있는 수는 5 뿐이다.
Set[1] : { 5 }
Set[2] : { ... }
Set[3] : { ... }
Set[4] : { ... }
Set[5] : { ... }
Set[6] : { ... }
Set[7] : { ... }
Set[8] : { ... }5를 2회 사용하는 Set[2]에는 어떤 수가 들어갈 수 있을 까? 5를 연속해서 쓰는 경우인 55와, Set [1]의 원소들 모두와 Set[1]의 원소들 모두가 사칙연산을 하는 경우가 있을 것이다. 좌측 피연산자와 우측 피연산자가 사칙연산을 모두 하여 집합에 삽입하는 연산을 편의상 ⨀ 연산자로 로 표현하겠다. 여기서 5 ⨀ 5 는 다음을 뜻한다.
Set[i].insert(5 + 5)
Set[i].insert(5 - 5)
Set[i].insert(5 * 5)
Set[i].insert(5 / 5)Set[1]에는 원소가 5 뿐이기 때문에 Set[2] 집합에는 5를 연속해서 쓰는 숫자인 55와 5 ⨀ 5의 모든 결과가 들어갈 것이다.
Set[1] : { 5 }
Set[2] : { 0 1 10 25 55 }
Set[3] : { ... }
Set[4] : { ... }
Set[5] : { ... }
Set[6] : { ... }
Set[7] : { ... }
Set[8] : { ... }Set[3]는 5를 3번 활용해서 만들 수 있는 수들의 집합이다. 먼저 5를 3번 연속해서 쓰는 숫자인 555가 들어갈 것이다. 그리고, N을 3번 사용해서 만든 집합은 N을 한번 사용해서 만든 수 들과, N을 두 번 사용해서 만든 수들을 활용해서 만들어진다. 때문에 다음과 같은 수 들이 들어갈 것이다.
for(int left : Set[1])
for(int right : Set[2])
left ⨀ right;
for(int left : Set[2])
for(int right : Set[1])
left ⨀ right;⨀ 는 모든 사칙연산을 수행한다. 사칙 연산 중 +, * 연산은 교환법칙이 성립하지만 -, / 연산은 교환 법칙이 성립하지 않는다. (Set[1] 원소들) ⨀ (Set[2] 원소들)의 연산과 (Set[2] 원소들) ⨀ (Set[1] 원소들)은 다른 연산이기 때문에 각각 실행해야 한다. 그 결과 Set[3]는 다음과 같을 것이다.
Set[1] : { 5 }
Set[2] : { 0 1 10 25 55 }
Set[3] : { -50 -20 -5 -4 0 2 4 5 6 11 15 20 30 50 60 125 275 555 }
Set[4] : { ... }
Set[5] : { ... }
Set[6] : { ... }
Set[7] : { ... }
Set[8] : { ... }그다음 Set[4]를 생각해 보자. Set[4]는 5를 4번 활용해서 만들 수 있는 수들의 집합이다. 그래서 먼저 5를 4번 연속해서 쓰는 숫자인 5555가 들어갈 것이다. 그리고 4는 [1 + 3] / [2 + 2] / [3 + 1] 이기 때문에 다음의 연산을 진행한다.
for(int left : Set[1])
for(int right : Set[3])
left ⨀ right;
for(int left : Set[2])
for(int right : Set[2])
left ⨀ right;
for(int left : Set[3])
for(int right : Set[1])
left ⨀ right;그 결과는 다음과 같을 것이다.
Set[1] : { 5 }
Set[2] : { 0 1 10 25 55 }
Set[3] : { -50 -20 -5 -4 0 2 4 5 6 11 15 20 30 50 60 125 275 555 }
Set[4] : { -550 -270 -250 -120 -100 -55 -54 -45 -30 -25 -24 -20 -15
-10 -9 -6 -5 -4 -3 -1 0 1 2 3 4 5 6 7 9 10 11 12 15 16
20 24 25 26 30 35 45 50 54 55 56 65 75 80 100 110 111
120 130 150 250 270 280 300 550 560 625 1375 2775 3025
5555 }
Set[5] : { ... }
Set[6] : { ... }
Set[7] : { ... }
Set[8] : { ... }N을 5회쓰는 경우는 마찬가지로 55555가 기본으로 들어갈 것이고, 5는 [1 + 4] / [2 + 3] / [3 + 2] / [4 + 1]로 표현할 수 있기 때문에 집합 간의 연산이 4번 필요하다. 이를 조금 일반화하면 다음과 같은 반복문이 될 것이다. 그리고 바텀업 방식이기 때문에 i번째 집합이 완성되면 그 즉시 number에 해당하는 수가 있는지 탐색할 수 있다.
Set[1].insert(N);
// N을 1회 에서 8회 사용할 경우
for(int i = 2; i < 9; i++){
Set[i].insert(initNumber); // initNumber는 N을 i회 연속해서 만드는 수
for(int j = 1; j < i; j++)
for(int left : Set[j])
for(int right : Set[i - j])
left ⨀ right;
// Set[i] 집합에 number가 있는지 확인. 있다면 i 반환 후 종료
if(Set[i].find(number) != Set[i].end())
return i;
}마지막으로 앞어 사칙연산의 교환 법칙을 언급하며, (Set[1] 원소들) ⨀ (Set[2] 원소들)의 연산과 (Set[2] 원소들) ⨀ (Set[1] 원소들)의 연산을 굳이 모두 진행해야 한다고 설명했다. -, / 연산은 교환 법칙이 성립하지 않기 때문에 위 두 연산을 모두 진행해야 하지만, +, * 연산은 교환 법칙이 성립하기 때문에 중복이 발생한다. 특히나 이 알고리즘에서는 연산을 진행 후 Set에 삽입하는 과정이 시간 복잡도의 가장 큰 영향을 미치기 때문에 중복을 줄여주면 효율이 좋아진다. 따라서 (Set[1] 원소들) ⨀ (Set[2] 원소들) 연산을 진행할 때 -, / 연산은 좌변과 우변을 바꿔서 한번 더 계산해준다. 정리하면 다음과 같은 방식이 될 것이다.
Set[1].insert(N);
for(int i = 1; i < 9; i++)
{
// 만약 i가 8이라면 j는 1, 2, 3, 4까지만 실행됨.
for(int j = 1; j <= (i / 2); j++)
{
for(int left : Set[j])
for(int right : Set[i - j])
{
Set[i].insert(left + right); // + 연산
Set[i].insert(left * right); // * 연산
// - 연산은 좌변과 우변을 교환하여 한번 더 진행
Set[i].insert(left - right);
Set[i].insert(right - left);
// / 연산은 좌변과 우변을 교환하여 한번 더 진행
if(right != 0)
Set[i].insert(left / right);
if(left != 0 )
Set[i].insert(right / left);
}
}
if(Set[i].find(number) != Set[i].end())
return i;
}실제로 중복을 제거한 후 계산량이 많은 테스트 케이스 4번과 8번에서 약 25% ~ 30% 정도 시간이 단축됨을 확인할 수 있다. 이상으로 설명을 마친다.
구현
#include <string>
#include <vector>
#include <set>
#include <array>
using namespace std;
int solution(int N, int number) {
// 반복문에서 계산의 편의를 위해 SetArray[0]은 사용하지 않음.
// SetArray[1] ~ [8]까지 사용
array<set<int>,9> SetArray;
// 각 집합에 N, NN, ... , NNNNNNNN 을 초기 값으로 삽입.
SetArray[1].insert(N);
for(int i = 2; i < 9; i++)
{
int initNumber = *(SetArray[i-1].begin());
initNumber = initNumber * 10 + N;
SetArray[i].insert(initNumber);
}
for(int i = 1; i < 9; i++)
{
// 만약 i가 8이라면 j는 1, 2, 3, 4가 실행됨.
for(int j = 1; j <= (i / 2); j++)
{
for(int left : SetArray[j])
for(int right : SetArray[i - j])
{
SetArray[i].insert(left + right); // + 연산
SetArray[i].insert(left * right); // * 연산
// - 연산은 좌변과 우변을 교환하여 한번 더 진행
SetArray[i].insert(left - right);
SetArray[i].insert(right - left);
// / 연산은 좌변과 우변을 교환하여 한번 더 진행
if(right != 0)
SetArray[i].insert(left / right);
if(left != 0 )
SetArray[i].insert(right / left);
}
}
if(SetArray[i].find(number) != SetArray[i].end())
return i;
}
return -1;
}