Inflearn Community Q&A

mch4737006777

asked

10-Week Completion C++ Coding Test | Algorithm Coding Test

7-A

7-A 한줄로 디버깅 하고 싶은데 혹시 이 부분 나눌 수 있을까요?

Written on

285

ret과 재귀로 호출하는 부분 최소 값으로 셋팅하는 결과를 실시간으로 보고 싶습니다.

ret = min(ret, tsp(i, visited | (1 << i)) + dist[here][i]);

이 부분 나눌 수 있을까요?

int temp = tsp(i,visited | (1<<i)) + dist[here][i]);

if(ret > temp) ret = temp;

이런식으로 나누고 싶은데 어떻게 건드려야될지 모르겠습니다..

c++코딩-테스트

Quiz

동적 계획법(Dynamic Programming)을 적용하기 위한 주요 조건은 무엇일까요?

탐욕적 선택 속성, 최적 부분 구조

최적 부분 구조, 중복되는 부분 문제

중복되는 부분 문제, 결정론적 결과

탐욕적 선택 속성, 메모이제이션

Answer 2

mch473700

Questioner

정말 감사드립니다!!

kundol

Instructor

안녕하세요 mch님 ㅎㅎ

#include <bits/stdc++.h> 
#define MAX_N 16
const int INF = 987654321;
using namespace std; 
int n, dp[MAX_N][1 << MAX_N], dist[MAX_N][MAX_N];
int tsp(int here, int visited){
    if(visited == (1 << n) - 1){
        return dist[here][0] ? dist[here][0] : INF;
    }
    int &ret = dp[here][visited];
    if(ret != -1) return ret;
    ret = INF;
    for(int i = 0; i < n; i++){
        if(visited & (1 << i)) continue;
        if(dist[here][i] == 0) continue;
        int temp = tsp(i, visited | (1 << i));
        cout << "temp : " << temp << "\n";
        ret = min(ret, temp + dist[here][i]);
        cout << (visited | (1 << i)) << " : " << ret << "\n";
    }
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> dist[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));
    cout << tsp(0, 1) << '\n';
    return 0;
}

한번 이렇게 해보시겠어요?

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

mch4737006777

asked

Ask a question