글 읽기 - 점화식이 잘못된 부분이 있을까요?

yosj0318 3년 전 0

3가지 경우로 생각했습니다.

0(OO) -> 연속 3번은 안되므로 다음은 건너 뛰어야됨 1(OX)로 이동

1(OX) -> 2칸 건너뛰기는 안되므로 다음은 밟아야함 2(XO)로 이동

2(XO) -> 현재까지 한번만 밟았으므로 다음은 밟아도 안밟아도 됨 0(OO) 또는 1(OX)로 이동

이라고 생각해 다음과 같이 작성했습니다.

마지막계단은 무조건 밟아야 하므로 마지막 비교도 현재 밟은 0(OO), 2(XO)만 비교했습니다.

혹시 틀린부분이 있을까요?

import java.util.Scanner;

public class Main{
	static int[] stair = new int[301];
	static int[][] score = new int[3][301];
	public static void main(String[] args){
		Main m = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		for(int i = 1 ; i <= n ; i++) {
			stair[i] = sc.nextInt();
		}

		/*
		 score[0] - OO -> X
		 score[1] - OX -> O
		 score[2] - XO -> O/X
		 */
		
		if(1 <= n) {
			score[0][1] = stair[1];
			score[1][1] = stair[1];
			score[2][1] = 0;
		}
		if(2 <= n) {
			score[0][2] = stair[1] + stair[2];
			score[1][2] = 0;
			score[2][2] = stair[2];
		}
		
		for(int i = 3 ; i <= n ; i++) {
			score[0][i] = score[2][i-1] + stair[i];
			score[1][i] = (score[0][i-1] > score[2][i-1]) ? score[0][i-1] : score[2][i-1]; 
			score[2][i] = score[1][i-1] + stair[i];
		}
		System.out.println((score[0][n] > score[2][n]) ? score[0][n] : score[2][n]);
		
	}
	
}

elbin98 3년 전 0

0(OO)에서 다음 원소가 앞에 것들보다 압도적으로 크다면 건너뛰지 말고 앞에것들을 바꾸어야겠지요

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

문제

문제

출처

ICPC

점화식이 잘못된 부분이 있을까요?

yosj0318 3년 전 0

elbin98 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말