글 읽기 - [10819] 차이를 최대로 질문드립니다.

sukth09 5년 전 0

해당 문제를 dfs로 풀었습니다.

각 인덱스를 node로 보고 모든 경우의 수를 다 방문하여 결과 값을 도출했습니다.

ex )

[Test Case]

0 1 2

[Tree]

- 0 - 1 - 2

- 2 - 1

root - 1 - 0 - 2

- 2 - 0

- 2 - 0 - 1

- 1 - 0

이런식으로 생각했습니다.

아래 코드는 맞은 코드인데요.

62번째 줄의

memset(visited, 0, sizeof(visited));

이 문장이 없으면 틀렸습니다가 나옵니다.

한참 고민해보고 질문게시판에 있는 반례를 모두 넣어봐도 답이 나옵니다.

대체 어떤 케이스에서 문제가 되는 것일까요?

//#define TEST_CASE
//#define DEBUG

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;

int N, ans;
int A[8];
int visited[8];
// 1이면 방문했음 0이면 방문하지 않음

int dfs(int A[], int index, int prev, int level) { 
    // 배열 A, 현재 인덱스, 이전 인덱스의 값, 트리의 레벨
    
	int res = 0; 
    // 리턴 값
	int sum = 0; 
    // 각 dfs의 값을 받아올 임시 변수

	if(level == N) { 
        // leaf 노드라면
		return abs(prev - A[index]);
	}
    
    
	visited[index] = 1; 
    // 마지막 정점을 만날 때 까지 중복된 노드를 방문하지 않기 위해
    
	for(int i = 0; i < N; i++) {
		if(i == index || visited[i]) continue;
        // 현재 인덱스거나 방문했던 노드면 건너뜀
        
		sum = abs(prev - A[index]) + dfs(A, i, A[index], level + 1);
        // leaf 노드부터 더해진 값 + 현재 계산 값 
        
		if(res < sum) {
            // max를 찾기위해
			res = sum;
		}
	}
	visited[index] = 0; // 다음 노드가 현재 인덱스의 노드를 방문할 수 있도록 하기 위해

	return res;
}

int main() {
	#ifdef TEST_CASE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif

	scanf("%d", &N);
	for(int i = 0; i < N; i++)
		scanf("%d", &A[i]);
	for(int i = 0; i < N; i++){
		memset(visited, 0, sizeof(visited));
        // 배열초기화
        
		int tmp = dfs(A, i, A[i], 1);
        // 0부터 N-1까지 dfs를 실행
		if(ans < tmp) {
            // max 를 찾기위해
			ans = tmp;
		}
	}
	printf("%d\n", ans);

	#ifdef TEST_CASE
	fclose(stdin);
	fclose(stdout);
	#endif

	return 0;
}

djm03178 5년 전 0

이 코드에서 memset만 주석치고 제출해봤는데, 둘 다 맞았습니다. 저걸 지워서 틀렸다면 어딘가 다른 곳도 고친 곳이 있으실 겁니다.

sukth09 5년 전 0

매번 친절한 답변 감사합니다.

다음에는 꼼꼼히 확인하고 올리겠습니다.

좋은 하루 되세요 ㅎㅎ

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

문제

문제

출처

ICPC

[10819] 차이를 최대로 질문드립니다.

sukth09 5년 전 0

djm03178 5년 전 0

sukth09 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말