글 읽기 - 테스트 해보면 다 맞는거 같은데 반례좀 알려주세요 ㅠㅠ

pillusion 6년 전 0

살려주세요 ㅠㅠ 백준 사이트는 어디서 틀렸는지 왜 안보여주죠? ㅠㅠ

import java.util.*;

public class Main {
	
	public static int maxNum;							// 계단의 최대 갯수
	public static int[] stairNum = new int[300];		// 각 계단 값
	public static int[] stairJumpCheck = new int[300];	// 한칸만 이동했을 경우 표시할 배열
	
	public static void dp(int p) {
		/*
		 * 	 로직 설명 : 왼쪽 부터 각 계단까지 오는데 최고의 값을 선택 (왼왼쪽, 왼쪽 중 선택)
		 */
		
		// 첫번째와 두번째는 정해져 있으므로 고정값
		if(p==0) {
			dp(p+1);
			return;
		}
		if(p==1) {
			stairNum[p] += stairNum[p-1];
			stairJumpCheck[p] = 1;
			dp(p+1);
			return;
		}
		
		// 맨 오르쪽 까지 도달 했을시 리턴
		if(p>=maxNum) {
			return;
		}

		if(stairNum[p-1] > stairNum[p-2] // 경우의 수가 왼쪽이 왼왼쪽 보다 클때
           && stairJumpCheck[p-1] != 1 // 왼쪽이 이미 한칸이동을 사용 안한경우
           && p != maxNum-2            // 맨 오른쪽에서 2번째가 아닌경우(맨오른쪽에서 2번째가 한칸이동을 사용하면 마지막에 못 도달 하므로)
           && stairNum[p-1] > stairNum[p+1] // 오른쪽보다 왼쪽이 클때 
          ) 
        {
			// 위와 같은 경우 왼쪽 계단 값을 지금 계단 값에 더하고 한칸이동 사용했다고 체크
			stairNum[p] += stairNum[p-1];
			stairJumpCheck[p] = 1;
		} else {
			stairNum[p] += stairNum[p-2];
		}
		
		dp(p+1);
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);	
		
		maxNum = sc.nextInt();
		
		for(int i=0; i<maxNum; i++) {
			stairNum[i] = sc.nextInt();
		}
		
		dp(0);
		
		System.out.println(stairNum[maxNum-1]);
		
		sc.close();
	}
}

ho94949 6년 전 1

31~38번째 라인의 dp식이 이해가 되지 않네요, 어떤 한 계단위에 있을 때는, 바로 전에 하나의 점프를 쓴 경우와 두번 점프를 쓴 경우 모두 고려가 되어야 하는데 고려가 되어있지 않네요.

pillusion 6년 전 0

현재 계단에서 왼쪽과 왼왼쪽중 큰것을 지금 계단에 더해서 지금 계단에서 얻을 수 있는 최대값을 구하도록 로직을 짰습니다.

두 번 점프 뛴 다음에는 한번을 뛰던 두번을 뛰던 상관없어서 고려를 안했는데..

혹시 두 번 점프 뛴다음 어떤 걸 고려해야 할까요???

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

문제

문제

출처

ICPC

테스트 해보면 다 맞는거 같은데 반례좀 알려주세요 ㅠㅠ

pillusion 6년 전 0

ho94949 6년 전 1

pillusion 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말