[프로그래머스] N으로 표현 (C++, Java)

카테고리

DFS

나만의 카테고리

DFS

문제 링크

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

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

 

요점

• 연산의 양을 많지 않게 하는 조건 + 전체 다 계산 필요 => DFS

참고 지식

• DFS
• Math.min()

풀이 (Java)

import java.util.*;

class Solution {
    // 8이하 값이므로
    final int MAX_COUNT = 9;
    int minAnswer = MAX_COUNT;
    
    public int solution(int N, int number) {
        dfs(N, number, 0, 0);
        
        if (minAnswer >= MAX_COUNT) {
            return -1;
        }
        
        return minAnswer;
    }
    
    private void dfs(int n, int answerNumber, int currentAnswer, int count) {
        if (count > 8 || answerNumber == currentAnswer) {
            minAnswer = Math.min(count, minAnswer);
            
            return;
        }
        
        int num = 0;
        
        for (int index = 0; index < MAX_COUNT; index++) {
            num = num * 10 + n;
            
            dfs(n, answerNumber, currentAnswer + num, count + 1 + index);
            dfs(n, answerNumber, currentAnswer - num, count + 1 + index);
            dfs(n, answerNumber, currentAnswer * num, count + 1 + index);
            dfs(n, answerNumber, currentAnswer / num, count + 1 + index);
        }
    }
}

풀이 (C++)

#include <string>
#include <algorithm>

using namespace std;

// 8이하 값이므로
int MAX_COUNT = 9;
int minAnswer = MAX_COUNT;

void dfs(int n, int answerNumber, int currentAnswer, int count) {
    if (count > 8 || answerNumber == currentAnswer) {
        minAnswer = min(count, minAnswer);
        
        return;
    }
    
    int num = 0;
    
    for (int index = 0; index < MAX_COUNT; index++) {
        num = num * 10 + n;
        
        dfs(n, answerNumber, currentAnswer + num, count + 1 + index);
        dfs(n, answerNumber, currentAnswer - num, count + 1 + index);
        dfs(n, answerNumber, currentAnswer * num, count + 1 + index);
        dfs(n, answerNumber, currentAnswer / num, count + 1 + index);
    }
}

int solution(int N, int number) {
    dfs(N, number, 0, 0);
        
    if (minAnswer >= MAX_COUNT) {
        return -1;
    }
    
    return minAnswer;
}

 

이 문제에서 가장 어려운 부분은 N이 5라면 55, 555, 5555를 만드는 방법을 몰라서 어려웠습니다. String으로 합쳐야 하나 했다가 for문과 (n = n * 10 + 첫 N)을 통해서 만들 수 있었습니다.

 

---

알고리즘 초보가 정리한 글입니다

더 좋은 방법이나 코드에 대한 코멘트 언제나 환영합니다!