[JS/알고리즘] DP : N으로 표현 (프로그래머스)

2021. 12. 14. 22:13·Programming/Algorithm

문제 설명

아래와 같이 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 합니다.
입출력 예Nnumberreturn
5 12 4
2 11 3
입출력 예 설명

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

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

 

 

문제 해결 방법

우선, DP라는 것에 주목해보자. DP의 대표적인 예제로 피보나치 수열이 있는데, 피보나치 수열의 다음 값 연산에서

이전 값들을 사용하는 것 처럼 다음 연산을 할 때, 이전 연산 들의 결과 값을 참조하는 방식이 DP이다.

쉽게 말해, 어떤 연산의 10번째 값을 구하기 위해서는 8번째와 9번째의 결과 값이 필요한 방식이다.

해당 문제도 이러한 논리로 접근하면 간단하게 해결할 수 있다.

5가 3개 사용된 경우 들은 5가 1번 사용된 경우 들과 2번 사용된 경우 들의 사칙 연산된 값 들의 집합이다.

2번 사용된 경우 들은 1번 사용된 경우를 사칙 연산 한 것이다.

해당 문제에서는 결과 값이 8 이상이라면 -1를 반환하게 하여 그 이상의 연산은 의미 없음을 알려주고 있어,

8개가 사용 되는 경우 까지만 연산 하면 된다.

 

 

해결 코드

//최대 사용 가능 횟수는 8회
//5, 55, 555 ... 55555555가 사칙연산 없이 가능한 숫자.
//3번 사용된 경우의 수는 2번 사용된 경우에 1번 사용된 경우를 사칙연산한 것.
//즉, 이전 횟수의 경우들을 조합하면 다음 횟수의 경우를 만들어 낼 수 있음.


function solution(N, number) {
    var answer = 0;
    let s = [];
    
    for (let i = 1; i<9; i++){
        s.push(new Set());
        let e = "";
        for (let j = 0; j<i; j++){
            e += String(N)
        }
        s[i-1].add(parseInt(e));
    }

    
   // 2 => (1,1)
   // 3 => (1,2)
   // 4 => (1,3) (2,2)
   // 5 => (1,4), (2,3)
    
    for (let i = 0; i<8; i++){
        for (let j = 0; j<i; j++){
            for (let e1 of s[j]){
                   for (let e2 of s[i-j-1]) //e1이 0부터 시작하기때문에 -1을 해줘야 함.
                       {
                           s[i].add(e1 + e2);
                           s[i].add(e1 - e2);
                           s[i].add(Math.floor(e1 / e2));
                           s[i].add(e1 * e2);
                       }
            }
        }
        for (let k of s[i]){
            if(k === number){
                return i+1; //0부터 배열이 시작하므로 +1 후 횟수 반환
            }
        }
    }
    //모두 실패
    return -1;
}
저작자표시 비영리 변경금지 (새창열림)

'Programming > Algorithm' 카테고리의 다른 글

[JS/알고리즘] 카카오 : 문자열 압축 (프로그래머스)  (0) 2021.12.21
[JS/알고리즘] 이분탐색 : 입국 심사 (프로그래머스)  (0) 2021.12.19
[JS/알고리즘] 탐욕 : 섬 연결하기 (프로그래머스)  (0) 2021.12.12
[JS/알고리즘] 탐욕 : 단속카메라 (프로그래머스)  (0) 2021.12.12
[JS/알고리즘] 탐욕 : 구명보트 (프로그래머스)  (0) 2021.12.05
'Programming/Algorithm' 카테고리의 다른 글
  • [JS/알고리즘] 카카오 : 문자열 압축 (프로그래머스)
  • [JS/알고리즘] 이분탐색 : 입국 심사 (프로그래머스)
  • [JS/알고리즘] 탐욕 : 섬 연결하기 (프로그래머스)
  • [JS/알고리즘] 탐욕 : 단속카메라 (프로그래머스)
박유상의 개발블로그
박유상의 개발블로그
개발블로그
  • 박유상의 개발블로그
    박유상의 개발블로그
    박유상의 개발블로그
  • 전체
    오늘
    어제
    • 전체 (134)
      • Who am I (10)
        • Portfolio (4)
        • Reminiscence (5)
        • Oversea (1)
        • SiliconValley (0)
      • React (36)
        • React Basic (15)
        • React Tech (5)
        • JavaScript (7)
        • TypeScript (3)
        • CSS&HTML (3)
        • Firebase (3)
      • NodeJS (1)
        • NodeJS Basic (1)
      • Flutter (55)
        • Flutter Widget Design (5)
        • Flutter Widget Basic (8)
        • Flutter Tech (18)
        • Flutter Issue (7)
        • Flutter Web (6)
        • About Flutter (2)
        • Firebase (1)
        • Dev Env (1)
        • Dart (7)
      • Programming (31)
        • Web (1)
        • General (0)
        • Algorithm (25)
        • Python (1)
        • VS Code (2)
      • Django (0)
  • 블로그 메뉴

    • Who I AM
    • React
    • NodeJS
    • Flutter
    • Programming
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    Redux
    Lingory
    DP
    플러터 웹
    DART
    파이썬
    map
    HTML
    github
    JavaScript
    flutter web
    Flutter
    react
    링고리
    포트폴리오
    탐욕법
    useRef
    리액트
    TypeScript
    CSS
    Python
    플러터
    알고리즘
    Firebase
    useTranslation
    useState
    프로그래머스
    JSON
    자바스크립트
    웹
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
박유상의 개발블로그
[JS/알고리즘] DP : N으로 표현 (프로그래머스)
상단으로

티스토리툴바