[프로그래머스(Programmers)][자바(java)] (Lv3) N으로 표현

 

programmers.co.kr/learn/courses/30/lessons/42895

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

 

문제 설명

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

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

입출력 예

N	number	return
5	12	4
2	11	3

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

 

문제 풀이

 

import java.util.LinkedList;
import java.util.List;

public class Solution {
	
	public int solution(int N, int number) {
		int c_min = -1, i, j;
		List<List<Integer>> dp = new LinkedList<>();
		for( i = 0; i < 8; i++ )
			dp.add( new LinkedList<>() );
		int s = 0;
		for( i = 0; i < 8; i++ ) {
			s = s * 10 + N;
			if( s == number )
				return i + 1;
			dp.get( i ).add( s );
		}
		for( i = 1 ; i < 8 ; i++ ) {
			for( j = 0 ; j < i ; j++ ) {
				for( int n1 : dp.get( j ) ) {
					for( int n2 : dp.get( i-j-1 ) ) {
						dp.get( i ).add( n1 + n2 );
						dp.get( i ).add( n1 - n2 );
						dp.get( i ).add( n1 * n2 );
						if( n2 != 0 ) dp.get( i ).add( n1 / n2 );
					}
				}
			}
			if( dp.get( i ).contains( number ) ) {
				c_min = i + 1;
				break;
			}
		}
		return c_min;
	}

}

 

*  동적계획법

-  List<Integer> dp.get( i )  :  i+1 개의 N으로 만들 수 있는 모든 수들  ( 0 <= i < 8 )
-  우선 dp.get( i )에 N을 i+1개 이어 붙인 수를 넣음
-  dp.get( i )에  dp.get( j )와 dp.get( i-j-1 )의 각 수들을 더해서 넣음
-  dp.get( i )을 차례로 탐색하며 number과 같은 수가 있는지 판단
   존재할 경우 i+1 리턴, 존재하지 않을 경우 -1 리턴