프로그래머스 N으로 표현

- 문제 설명

 

N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하는 solution 함수 작성

 

 

- 입력

 

1) N (1 <= N <= 9)

2) number (1 <= number <= 32000)

 

 

- 출력

 

N 사용횟수의 최솟값 (최솟값이 8보다 크면 -1을 return)

 

 

* 문제 풀이의 핵심

 

문제를 해결하지 못하여 여러가지 해답을 본 결과 DFS를 활용한 방법만 이해할 수 있었고 크게 3가지 쟁점으로 나누어 분석하였습니다. (이해하는데 참고한 사이트는 하단에 링크 표시하였습니다.)

 

 

1. DFS를 통해 시간안에 해결할 수 있을까

 

재귀적으로 모든 경우를 탐색해도 최대 깊이는 8이므로 1초 이내에 작업을 완료할 수 있을 것이라고 생각하였습니다.

 

실제 -1 값이 나오는 경우를 완전 탐색이라고 기준을 잡았을 때 계산량은 약 1250만번으로 시간내에 작업을 완료할 수 있었습니다.

 

 

2. 어떻게 DFS 탐색을 통해 모든 경우의 수를 계산할 수 있을까

 

1) N은 8번 이상 사용하거나 결과 값을 찾은 경우 함수를 종료해야 하는 기저사례를 작성

 

if (cnt > 8) return INF;
if (number == res) return cnt;

 

2) N의 자릿수를 늘려가면서 사칙연산을 적용하면 모든 경우의 수 계산가능

 

i는 N을 사용한 횟수, dfs함수는 사칙연산 적용

 

int i, next = 0;
for (i = 1; i <= 8; i++) {
  next = next * 10 + N;
  ret = min(ret, dfs_search(N, number, res + next, cnt + i));
  ret = min(ret, dfs_search(N, number, res * next, cnt + i));
  ret = min(ret, dfs_search(N, number, res / next, cnt + i));
  ret = min(ret, dfs_search(N, number, res - next, cnt + i));
}

 

* 이 경우 number의 범위를 벗어난 0 또는 음수 값을 기준으로 계속 재귀를 반복하지만 중간 값이 범위를 벗어난 값일 수 있으므로 res의 값을 number의 범위로 제약을 두게되면 실패한다.

 

 

3. 전역변수를 사용하지 않고 해답을 얻을 수 있을까

 

1) dfs의 리턴 값은 N의 사용횟수를 리턴하도록 설정

 

2) dfs 함수 내에서 min 함수를 통해 리턴된 값과 최대 값이 지정된 ret 값과 비교해서 작은 값이 N 최소 사용 횟수

 

위의 방식을 재귀적으로 반복하면 결과적으로 최솟값이 리턴된다.

 

 

- 소스코드

 

#include<iostream>
#include<algorithm>

using namespace std;

const int INF = 98654321;

int dfs_search(int N, int number, int res, int cnt) {
	if (cnt > 8) return INF;
	if (number == res) return cnt;

	int ret = INF;

	int i, next = 0;
	for (i = 1; i <= 8; i++) {
		next = next * 10 + N;
		ret = min(ret, dfs_search(N, number, res + next, cnt + i));
		ret = min(ret, dfs_search(N, number, res * next, cnt + i));
		ret = min(ret, dfs_search(N, number, res / next, cnt + i));
		ret = min(ret, dfs_search(N, number, res - next, cnt + i));
	}

	return ret;
}

int solution(int N, int number) {
	int answer = dfs_search(N, number, 0, 0);
	if (answer == INF) {
		return -1;
	}
	return answer;
}

 

 

- 문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42895

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

 

 

- 제출한 코드

 

 

>  백준 아이디 : canoe726

>  사용언어 : C++

>  에디터 : Visual Studio 2017

>  궁금한점은 댓글로 남겨주세요

 

 

- 참고 : https://mungto.tistory.com/61