[고득점Kit][DFS][DP] N 으로 표현 ⭐⭐⭐

Date: 2020.10.24 Updated: 2020.10.24

카테고리: Programmers

[DFS][DP] N 으로 표현

난이도 ⭐⭐⭐

문제

👩🏽 DFS 풀이

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void DFS(int& answer, int N, int target, int calc, int depth)
{
    if (calc == target)
    {
        answer = min(answer, depth);
        return;
    }
    
    int operand = 0;
    for(int i = 1; i <= 8 - depth; i++)
    {
        operand = operand * 10 + N;
        
        DFS(answer, N, target, calc + operand, depth + i);
        DFS(answer, N, target, calc - operand, depth + i);
        DFS(answer, N, target, calc * operand, depth + i);
        DFS(answer, N, target, calc / operand, depth + i);
    }
    
    return;
}

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

이 문제의 포인트
- 1️⃣ 최소값이 8 을 넘어가면 -1을 리턴한다는 조건이 있다.
  - N의 개수는 총 8번까지만 허용된다.
- 2️⃣ 재귀 깊이는 현재까지 사용된 N 개수라고 볼 수 있다.
  - 종료 조건
    - 성공 조건 👉 따라서 number(target)와 일치하는 값을 찾았다면 해당 재귀 단계( = 현재까지 쓰인 N의 개수)와 answer 중 작은 것을 answer로 업뎃하고 리턴한다. answer엔 최소 값이 들어가야 하기 때문에!
      - answer는 & 참조 타입으로 넘겨서 모든 재귀 단계에서 공유할 수 있다.
    - 실패 조건 👉 재귀 단계( = 현재까지 쓰인 N의 개수)가 8 에 도달할 때까지 if (calc == target) 에 걸리지 못한 상태라면 그냥 리턴한다. 즉 N이 8 개까지 모두 다 쓰였는데 아직도 target을 찾지 못한 경우이다. 이 경우엔 for문도 조건에 안맞아 돌지 못한다. 따라서 for문 아래의 return을 만나게 된다.
  - 재귀 단계의 깊이는 현재까지 사용된 N 개수와 동일하다.
  - for 문의 반복 횟수는 추가로 붙일 수 있는 N 개수와 동일하다. 현재의 재귀 단계가 3 이면 (depth가 3 이면) N이 현재 단계까지 3 개 쓰였다는 것이므로 앞으로 8 - 3 = 5 개의 N개를 더 쓸 수 있다. (8 - depth)
    - 현재 8 - depth 값이 5 이라면 즉, 현재 단계(depth가 3, N 현재까지 3 개 쓰임)를 기준으로 앞으로 5 개의 N을 사용할 수 있다면 operand는 for문 반복마다 각각 N, NN, NNN, NNNN, NNNNN 로 업데이트 된다.
      - 현재 단계가 3 이라면
        
        operand가 N 으로 업데이트 되었다면 3 + 1 = 4 개의 N이 쓰이게 되는 것이므로 이제 현재까지의 calc에 N을 사칙연산하여 4 단계로 넘어간다.(현재까지 N이 4 개 쓰였다는 의미에서) 다음 단계에서의 for문은 8 - 4 = 4 번 돌게 될 것이다.
        
        operand가 NN 으로 업데이트 되었다면 3 + 2 = 5 개의 N이 쓰이게 되는 것이므로 이제 현재까지의 calc에 NN을 사칙연산하여 5 단계로 넘어간다.(현재까지 N이 5 개 쓰였다는 의미에서) 다음 단계에서의 for문은 8 - 5 = 3 번 돌게 될 것이다.
        
        operand가 NNN 으로 업데이트 되었다면 3 + 3 = 6 개의 N이 쓰이게 되는 것이므로 이제 현재까지의 calc에 NNN을 사칙연산하여 6 단계로 넘어간다.(현재까지 N이 6 개 쓰였다는 의미에서) 다음 단계에서의 for문은 8 - 6 = 2 번 돌게 될 것이다.
        
        operand가 NNNN 으로 업데이트 되었다면 3 + 4 = 7 개의 N이 쓰이게 되는 것이므로 이제 현재까지의 calc에 NNNN을 사칙연산하여 7 단계로 넘어간다.(현재까지 N이 7 개 쓰였다는 의미에서) 다음 단계에서의 for문은 8 - 7 = 1 번 돌게 될 것이다.
        
        operand가 NNNNN 으로 업데이트 되었다면 3 + 5 = 8 개의 N이 쓰이게 되는 것이므로 이제 현재까지의 calc에 NNNNN을 사칙연산하여 8 단계로 넘어간다.(현재까지 N이 8 개 쓰였다는 의미에서) 다음 단계에서의 for문은 8 - 8 = 0 번 돌게 될 것이다.
        
        즉 for문을 돌지 않게 됨. N이 8개까지 모두 다 쓴 이 때에 if (calc == target)에 걸리지 못하면 함수 맨 아래의 return을 만나게 된다. 즉, 이런 경우엔 answer가 업데이트 되지 못 함.
    - 현재의 재귀 단계에서의 operand를 기준으로 현재까지 누적 계산해온 값 calc 에대가 차례 대로 operand를 사칙연산하여 각각 4 가지 깊이 탐색을 진행하면 된다!
      - 각 재귀 호출 마다 지나온 calc들은 독립적으로 달라야 하기 때문에 참조로 넘기지 않는다. depth도 마찬가지.
- 3️⃣ answer는 9 로 초기화 해둔다. DFS 함수를 돌리는 동안 if (calc == target) 에 한번도 걸리지 못했다면 answer는 한번도 업데이트 되지 못한 것이다.
  - 일치하는게 아예 없는게 아니라 N을 8 개 이하로 사용해야 한다는 제한 내에서 사칙연산하는 모든 경우의 수에서 number와 일치한적이 한번도 없었다는 얘기므로 이건 최소값이 9 를 넘는다는 것을 의미한다.
    - 따라서 DFS 함수가 최종적으로 모두 리턴되었을 때 answer가 그대로 9 라면 -1 을 리턴한다.

👩🏼 Dynamic Programming (동적 계획법) 풀이

풀이 출처 : 하글님 블로그

DP로 푸는 방법은 이 분의 블로그에서 DP 로 푸신 풀이를 보고 이해할 수 있었다! DP 로는 어떻게 풀어야하는지 감을 못 잡았는데 이 분의 설명을 보고 무릎을 탁 치고 이해…

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

int solution(int N, int number) {
  int const min = 9;
	vector<set<int>> v(min);

	for (int i = 1; i < min; i++) {
    
    // 1 열 (행과 동일한 5, 55, 555 등등)
    int result = 0;
    for (int j = 0; j < i; j++)
		  result = result * 10 + N;
		v[i].insert(result);
        
    // 1열이 아닌 그 외의 열
		for (int j = 1; j < i; j++) {
			for (int k = 1; k < i; k++) {
				if (j + k == i) {
					for (auto a : v[j]) {
						for (auto b : v[k]) {
							v[i].insert(a + b);
							v[i].insert(a * b);
							if (a > b) v[i].insert(a - b);
							if (a < b) v[i].insert(b - a);
							if (b > 0) v[i].insert(a / b);
							if (a > 0) v[i].insert(b / a);
						}
					}
				}
			}
		}
	}
    
    // 최소값 도출
	for (int i = 1; i < min; i++) {
		for (auto j : v[i]) if (j == number) {
			return i;
		}
	}
	
	return -1;
}

동적계획법 👉 점화식 세우는게 가능해야 한다.

큰 문제를 작은 문제들로 해결할 수 있어야 한다. ex) 피보나치 수열, 이항 계수 처럼.
큰 문제의 최적화는 곧 작은 문제의 최적화와 같다.
Bottom-Up 방식으로 밑에서부터, 앞에서부터 차례대로 문제를 풀고 결과를 저장한다.
- 이 문제를 작은 문제로서 필요로 하는 다른 큰 문제를 풀 때, 해당 작은 문제를 다시 풀 필요없이 결과만 가져올 수 있도록.

  int const min = 9;
	vector<set<int>> v(min);

벡터 v 1 ~ 8 행을 가진다. 추후 인덱스를 행과 맞추기 위해 사이즈를 9 로 선언하신 것 같다. 행마다 각각 사이즈가 다른 set이 있다. set을 벡터의 원소로 하면 중복 값을 배제할 수 있다.

1 행은 5 이렇게 1 개로 만들 수 있는 모든 값들을 저장한다.
- 1 행은 그 자체로 5 하나만 있을 수 있게 된다.
- 1 행 1 열은 5 고정. set 의 크기는 1
2 행은 55 이렇게 2 개로 만들 수 있는 모든 값들을 저장한다.
- 1 열은 55 고정.
- 점화식 👉 B2 = (B1 + B1) + (B0 + B2)
  - 5 2 개로 만들 수 있는 모든 경우의 수인 2 행 원소들은 ✨2행 1열의 55를 제외하면 (B0 + B2)✨ 5 1 개로 만들 수 있는 모든 경우의 수인 1행과 5 1 개로 만들 수 있는 모든 경우의 수인 1행을 사칙연산한 모든 경우의 수다. (B1 + B1)
3 행은 555 이렇게 3 개로 만들 수 있는 모든 값들을 저장한다.
- 1 열은 555 고정.
- 점화식 👉 B3 = (B1 + B2) + (B0 + B3)
  - 5 3 개로 만들 수 있는 모든 경우의 수인 3 행 원소들은 ✨3행 1열의 555를 제외하면 (B0 + B3)✨ 5 1 개로 만들 수 있는 모든 경우의 수인 1행과 5 2 개로 만들 수 있는 모든 경우의 수인 2행을 사칙연산한 모든 경우의 수다. (B1 + B2)
4 행은 5555 이렇게 4 개로 만들 수 있는 모든 값들을 저장한다.
- 1 열은 5555 고정.
- 점화식 👉 B4 = (B1 + B3) + (B2 + B2) + (B0 + B4)
  - 5 4 개로 만들 수 있는 모든 경우의 수인 4 행 원소들은 ✨4행 1열의 5555를 제외하면 (B0 + B4)✨ 5 1 개로 만들 수 있는 모든 경우의 수인 1행과 5 3 개로 만들 수 있는 모든 경우의 수인 3행을 사칙연산한 모든 경우의 수와 (B1 + B3) 5 2 개로 만들 수 있는 모든 경우의 수인 2행과 5 2 개로 만들 수 있는 모든 경우의 수인 2행을 사칙연산한 모든 경우의 수다. (B2 + B2)
이런식 ! 마치 피보나치 수열이나 이항계수처럼! 작은 문제로 쪼개질 수 있다.
- 5 3개로 만들 수 있는 모든 경우의 수는, 5 2개로 만들 수 있는 모든 경우와 5 1개로 만들 수 있는 모든 경우의 수들을 사칙연산 한것과 같다. 여기에 더해 5 3 개로 만들 수 있는 모든 경우의 수를 사칙연산 해준것과도 같다.

for (int i = 1; i < min; i++) {

**각 v[i]행의 set에 값을 저장하여 완성해나간다.

1 행부터 8 행까지 살펴보자. i는 행을 뜻한며 v[i]에는 i개의 N개를 사용하여 사칙연산한 값들을 차례로 저장해두는 set이 있다.

// 1 열 (행과 동일한 5, 55, 555 등등)
int result = 0;
for (int j = 0; j < i; j++)
		result = result * 10 + N;
v[i].insert(result);

현재 i는 행을 뜻함. 더 큰 fr문 for (int i = 1; i < min; i++)

i행의 모든 1 열은 i개의 N개를 하나의 수로 단독으로 사용한 값이다. 1 행 1 열은 5, 2행 1열은 55, 3행 1열은 555 등등.. 먼저 모든 행의 1 열에 넣어주자. i번 만큼 result = result * 10 + N; 를 진행하여 result를 만들고 이를 i행의 set 에 처음으로 추가 해주면 된다.

    // 1열이 아닌 그 외의 열
		for (int j = 1; j < i; j++) {
			for (int k = 1; k < i; k++) {
				if (j + k == i) {
					for (auto a : v[j]) {
						for (auto b : v[k]) {
							v[i].insert(a + b);
							v[i].insert(a * b);
							if (a > b) v[i].insert(a - b);
							if (a < b) v[i].insert(b - a);
							if (b > 0) v[i].insert(a / b);
							if (a > 0) v[i].insert(b / a);
						}
					}
				}
			}
		}

현재 i는 행을 뜻함. 더 큰 fr문 for (int i = 1; i < min; i++)

점화식 👉 N을 i개 사용하여 만드는 모든 경우의 수(i행)는 N을 j개 사용하여 만드는 모든 경우의 수((j행)와 N을 i - j개 사용하여 만드는 모든 경우의 수( (k행)를 사칙연산 한 것과 같다.

					for (auto a : v[j]) {
                      for (auto b : v[k]) {
                          v[i].insert(a + b);
                          v[i].insert(a * b);
                          if (a > b) v[i].insert(a - b);
                          if (a < b) v[i].insert(b - a);
                          if (b > 0) v[i].insert(a / b);
                          if (a > 0) v[i].insert(b / a);
                      }
                  }

j,k는 1 ~ i 범위를 가지며

j + k 는 i이다.

for (int j = 1; j < i; j++) {
        for (int k = 1; k < i; k++) {
            if (j + k == i) {

동적 계획법 중요 포인트 👉 큰 문제의 최적화는 곧 작은 문제의 최적화와 같다.

궁극적인 목표는 number와 같은 값을 찾는 것이다. number는 1 이상인 양수이므로 각각의 사칙 연선 결과가 양수인 것만 저장하도록 할 것이다. number가 큰 문제라면 number의 구성요소인 작은 문제들 또한 양수여야 하기 때문이다. 따라서 빼기와 나누기의 경우 음수가 되지 않도록, 예외를 일으키지 않도록 한다.

    // 최소값 도출
	for (int i = 1; i < min; i++) {
		for (auto j : v[i]) if (j == number) {
			return i;
		}
	}

벡터 v의 모든 값을 차례대로 앞에서 부터(1행부터, 1열부터) 검사하여 number와 동일한 원소 값을 찾아낸다. 그럼 그 값은 자연스럽게 최소값이다. 앞에서부터 찾았으니까! (i행은 N을 i번 사용한 모든 경우의수가 모여 있으므로 앞의 행부터 찾아서 최초로 찾았다면 당연히 최소 값이다.) 따라서 그 때의 행 i를 리턴한다. for문 다 돌도록 찾지 못했다면 -1 리턴

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️

[고득점Kit][DFS][DP] N 으로 표현 ⭐⭐⭐

[DFS][DP] N 으로 표현

문제

👩🏽 DFS 풀이

👩🏼 Dynamic Programming (동적 계획법) 풀이

Programmers 카테고리 내 다른 글 보러가기

댓글 남기기

최근 글 10 개 :)