서론
오늘의 코딩 테스트 문제는 '프로그래머스'의 "N으로 표현"이다. 동적 계획법 연습을 위해 선택했다.
문제 분석
문제의 핵심은 다음과 같다:
•
숫자 N을 사용해 사칙연산으로 number를 표현
•
N을 연속해서 사용 가능 (예: NN, NNN)
•
괄호 사용 가능, 나눗셈의 나머지는 무시
•
N 사용 횟수가 8 초과면 -1 반환
접근 방식
동적 계획법, 그 중에서도 타뷸레이션 방식으로 접근했다. 이유는 다음과 같다:
1.
작은 부분 문제의 해결책으로 큰 문제를 해결할 수 있음
2.
중복 계산을 피할 수 있어 효율적
구현
#include <vector>
using namespace std;
int solution(int N, int number) {
vector<vector<int>> tb(9);
tb[0].push_back(N);
auto it = tb.end();
for (int i=11111111; i>=1; i=i/10){
(--it)->push_back(i*N);
}
for (int i=2; i<=8; i++)
{
for (auto q: tb[i-1])
{
if (q!=0)
tb[i].push_back(N / q);
tb[i].push_back(q + N);
tb[i].push_back(q - N);
tb[i].push_back(N - q);
tb[i].push_back(q * N);
tb[i].push_back(q / N);
}
for (auto q: tb[i])
if (q==number)
return i;
}
return -1;
}
C++
복사
1차 구현에서는 실수했다. 새로운 연산 대상이 항상 N이라고 가정했는데, 이는 잘못됐다.
55 * 55 같은 경우를 고려하지 않은 것이다.
2차 구현에서 이를 수정했다. 코드는 다음과 같다:
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int solution(int N, int number) {
vector<vector<int>> tb(9);
tb[1].push_back(N);
for (int i=1; i<=8; i++)
{
int n = N;
for (int j=1; j<i; j++)
{
for (auto q: tb[i-j])
{
if (q!=0)
tb[i].push_back(n / q);
tb[i].push_back(q + n);
tb[i].push_back(q - n);
tb[i].push_back(n - q);
tb[i].push_back(q * n);
tb[i].push_back(q / n);
}
n = (n * 10) + N;
}
tb[i].push_back(n);
for (auto q: tb[i])
if (q==number)
return i;
}
return -1;
}
C++
복사
회고
1.
DP에서 하위 문제 정의에 시간이 너무 오래 걸렸다. 이 부분은 개선이 필요하다.
2.
재귀적 접근도 가능했을 텐데, 타뷸레이션만 고집한 게 아쉽다.
3.
오버플로우를 걱정했는데 다른 풀이를 보니 발생하지 않았다. 잘못 예측한 것 같다.
4.
DP는 항상 문제 정의에서 시간을 많이 쓰는 것 같다. 좀 더 많은 문제들을 접하다 보면, 직관으로 정의할 수 있게 되려나?
