N으로 표현
문제정의
N으로 표현하기
자연수 N을 최대 8개까지 써서 사칙연산으로 주어진 수를 표현할 수 있는지 보는 문제이다. 만약 표현할 수 있다면 표현할 수 있는 수 중에 가장 작은 사용횟수를 출력해야 한다.
문제풀이
전체 코드는 다음과 같다. 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36public class NExpress {
//프로그래머스 문제풀이 level3 n으로 표현
static int answer = -1;
public static void main(String[] args) {
int N = 4, number = 17;
ReturnMin(0, 0, number, N);
System.out.println(answer);
}
public static void ReturnMin(int res, int cnt, int number, int N)
{
int temp = N;
if(cnt > 8)
answer = -1;
if(res == number)
{
if(answer == -1 || answer > cnt)
answer = cnt;
}
else
{
for(int i = 0; i < 8-cnt; i++)
{
ReturnMin(res+temp, cnt+i+1, number, N);
ReturnMin(res-temp, cnt+i+1, number, N);
ReturnMin(res*temp, cnt+i+1, number, N);
ReturnMin(res/temp, cnt+i+1, number, N);
temp = temp*10+N;
}
}
}
}temp부분에서 실수를 했다. 가령 1111+1111는 2222가 나와야 하는데 필자는 1111+1111을 계산하지 않고 끝내버리는 오류가 있었기 때문이다. 문제점을 알았으니 다행이다. 일단 코드 설명을 해보면 res는 현재까지 계산한 값을 의미하고 cnt는 사용횟수이다. number는 만들고자 하는 값이다.
재귀의 종료 조건은 사용횟수가 8을 넘어가면 답이 없는 것이므로 answer에 -1을 한다. 다른 경우는 8번안에 숫자가 만들어진다면 answer가 -1이거나 cnt보다 answer가 큰 경우 답을 cnt로 한다. 그것도 아니라면 사칙연산을 추가로 진행해야 한다. 사용할 수 있는 횟수만큼 N을 뒤에 붙여가며 더해간다. 예를들면 5를 4번쓸 수 있으면 [5,55,555,5555]로 사칙연산을 하는 것이다.
시간 복잡도는 최대 8번이라는 조건이 있기 때문에 \(O(4^8)\)이므로 \(O(1)\)로 나타낼 수 있다.
테스트
동적계획법으로 푸는 방법을 몰라서 재귀를 사용하였는데, 이런 경우 대게 테스트 케이스가 커서 골치 아픈 경우가 많다. 하지만 이 문제는 8이라는 제한 횟수가 있어서 그런지 시간 초과가 나는 일은 없었다. 재귀함수를 짤 때 종료조건에 대해 꼼꼼히 생각해봐야겠다.