글 읽기 - 다시 여쭤봅니다 ㅜㅜ 제가 해결한방식은 DP라고 볼수 없는가요?

minhas2 6년 전 0

안녕하세요 동적프로그래밍을 공부하고있는 한 사람입니당..

문제를 해결하긴했는데 하는 내내 이게 백트랙킹같은 느낌이 들어서요..

사실 이론적으로는 동적프로그래밍과 백트랙킹을 구분할 수 있는데

구현에서의 다른점을 모르겠습니다..

이웃하는 집과 중복하는 색깔을 피하는 상황을 제외하고 모든 경우의수를 다 탐색한다는 점에선 백트랙킹같기도 하고요...

다른분들 푸는방식을 보니까 min함수를 이용해서 for문 하나로 심플하게 푸셨던데..

전 for문에 재귀호출까지 해버리니까 풀고나서도 찜찜해서 질문드립니다...!

동적프로그래밍엔 맞지않는 답일까요?..

아 그리고 코드보시고 이런식으로 구현하면 안되는데.. 싶은 거슬리는 문장(?)이 보이시면

피드백 환영(감사)합니다!

// ACM_1149.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//

#include "stdafx.h"
#include <iostream>

using namespace std;

int N;

int solve(int num, int sum, int** inputA,int neighborNum) // num : 집 A,B,C... / neightborNum : num-1번째 집에 칠해진 색깔인덱스
{
	static int result = 2147483647;

	if (num == N) {
		if (result > sum) {
			result = sum;
		}
		
		return -1;
	}
	
		for (int i = 0; i < 3; i++) {
			if (num != 0) {
				if (neighborNum== i) {
					continue;
				}
				else {
					solve(num + 1, sum + inputA[num][i], inputA,i);
				}
			}
			else { // num==0인경우
				solve(num + 1, sum + inputA[num][i], inputA,i);
			}
		}

		return result;
	
}

int** input(int N) {
	int** input = new int*[N];
	for (int i = 0; i < N; i++) {
		input[i] = new int[3];

		for (int j = 0; j < 3; j++)
			cin >> input[i][j];
	}

	return input;

}

int main()
{
	cin >> N;

	int** inputArray;
	inputArray = input(N);

	cout << solve(0, 0, inputArray,-1);

    return 0;
}

yukariko 6년 전 1

동적 계획법은 부분문제의 답으로 전체문제의 답을 구하는 알고리즘입니다. 이를 이용하면 모든 경우의수를 다 살펴보지 않아도 정의한 부분문제의 답들을 가지고 문제를 해결할 수 있습니다.

재귀에서는 메모이제이션을 통해 DP를 구현할 수 있습니다. 쉽게말해 부분문제의 답을 캐싱하여 구한 답을 재사용하는것이죠.

이코드는 가능한 모든경우를 탐색하여 답을 구합니다.

따라서 DP가 아닌 완전탐색, 백트래킹 코드라 할 수 있을것 같습니다.

minhas2 6년 전 0

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

다시 여쭤봅니다 ㅜㅜ 제가 해결한방식은 DP라고 볼수 없는가요?

minhas2 6년 전 0

yukariko 6년 전 1

minhas2 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말