글 읽기 - 고수님들 어떤 케이스가 안되는지좀 알려주세요

stompesi 7년 전 0

고수님들 어떤 케이스가 안되는지좀 알려주세요..

도저희 모르겠네요 ㅠ

import java.util.Scanner;

public class Main1932 {
	private static Scanner scanner = new Scanner(System.in);
	
	public static void main(String[] args) {
		int i, j;
		int n = scanner.nextInt();
		int[][] arr = new int[n][n];
		int[][] max = new int[n][n];
		int totalMax = 0;
		
		for(i = 0 ; i < n ; i++) {
			for(j = 0 ; j <= i ; j++) {
				arr[i][j] = scanner.nextInt();
			}
		}
		if(n == 1) {
			System.out.println(totalMax);
			return;
		}
		
		for(i = 0 ; i < n ; i++) {
			for(j = 0 ; j < n ; j++) {
				max[i][j] = 0;
			}
		}
		
		totalMax = max[0][0] = arr[0][0];
		for(i = 1 ; i < n - 1 ; i++) {
			for(j = 0 ; j <= i ; j++) {
				max[i][j] = arr[i][j];
				if(j == 0) {
					max[i][j] += Math.max(max[i-1][j], max[i-1][j+1]); 
				} else {
					max[i][j] += Math.max(max[i-1][j-1], Math.max(max[i-1][j], max[i-1][j+1]));
				}
				totalMax = Math.max(totalMax, max[i][j]);
			}
		}
		System.out.println(totalMax);
	}
}

tofhddl9 7년 전 1

일단 n=1일때 totalmax=0를 출력하고 종료하는 케이스도 있을것이구요.

삼각형에서 내려오면서 윗줄의 max값 3개중 가장 큰 것을 더해주시는데 내려오는 루트는 2개인 것 같네요.

또 for문이 i<n-1 인데 i<n까지 돌아야 마지막 줄까지 계산 할 수 있지 않을까요?

모바일로 본거라 틀릴수도 있지만... 코드 따라가시다가 어려우시면 디버깅 추천드려요

stompesi 7년 전 0

혹시 , n이 1이면 0이 아니라는 소리이신가요?

현재 단계에서 내려왔을때 까지 선택된 수의 합을 찾는거라 1이면 선택한 수가 없어서 0이아니인가요 ?

문제를 잘 이해를 못하고 있는것같네요.

stompesi 7년 전 0

다시 C언어로 바꾸어보았습니다...

내려갈수 있는방법은0,0 에서 오른쪽, 왼쪽 대각선으로 내려가니

입력을 다음과 같이.. 입력하였을때

3 8

8 1 0

2 7 4 4

4 5 2 6 5

------------

최대 경로는 다음과같고..

0 15

23 0 15

0 30 0 19

34 0 32 0 24

맨 마지막까지 선택한 최대의 값은 30이므로 30을 출력한다. 아닌가요?ㅠㅠ 몇번을 실패하는지모르겟네요 ㅠㅠ

#include <stdio.h>

int main() {
    int n;
    int i, j;
    int step[500][500];
    int max_step[500][500];
    int total_max = 0;
    int index = 0;
    scanf("%d", &n);
    
    for(i = 0 ; i < n ; i++) {
        for(j = 0 ; j <= i ; j++) {
            scanf("%d", &step[i][j]);
            max_step[i][j] = 0;
        }
    }
    
    max_step[0][0] = step[0][0];
    
    if(n == 1) {
        printf("%d", max_step[0][0]);
        return 0;
    }
    for(i = 1 ; i < n ; i++) {
        if(i % 2 == 1) {
            for(j = 1 ; j <= i ; j+=2) {
                if(max_step[i - 1][j - 1] > max_step[i - 1][j + 1]) {
                    max_step[i][j] = max_step[i - 1][j - 1] + step[i][j];
                } else {
                    max_step[i][j] = max_step[i - 1][j + 1] + step[i][j];
                }
            }
        } else {
            for(j = 0 ; j <= i ; j += 2) {
                if(j == 0) {
                    max_step[i][j] = max_step[i - 1][j + 1] + step[i][j];
                } else {
                    if(max_step[i - 1][j - 1] > max_step[i - 1][j + 1]) {
                        max_step[i][j] = max_step[i - 1][j - 1] + step[i][j];
                    } else {
                        max_step[i][j] = max_step[i - 1][j + 1] + step[i][j];
                    }
                }
            }
        }
    }
    
    for(i = 0 ; i < n ; i++) {
        if(max_step[n - 1][i] > total_max) {
            index = i;
            total_max = max_step[n - 1][i];
        }
    }
    
    printf("%d\n", total_max - step[n - 1][index]);
    return 0;
}

tofhddl9 7년 전 1

우선, "맨 위층부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로"는

맨 위층부터 맨 아래층까지 선택한 것들의 최대값을 구하는 것이므로

n=1일때는 그 한 층의 크기가 답이 됩니다.

예를 들어서,

입력이 1

10 일경우

답으로 10을 출력해야 합니다.

잘못 이해하신 중요한 또 다른 한 가지는

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 라는 입력은

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 의 파스칼 삼각형을 나타낸 것입니다.

따라서 최대 경로의 누적값은 다음과 같겠죠~?

  7
10   15
18    16 15
....
....

stompesi 7년 전 1

감사합니다.. 너무멍청하게 생각햇네요 ㅎㅎ 덕분에 풀었습니다!!

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

문제

문제

출처

ICPC

고수님들 어떤 케이스가 안되는지좀 알려주세요

stompesi 7년 전 0

tofhddl9 7년 전 1

stompesi 7년 전 0

stompesi 7년 전 0

tofhddl9 7년 전 1

stompesi 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말