글 읽기 - 2579 계단오르기 도저히 모르겠습니다.

quf9484 4년 전 0

질문에 있는 다른 예제들을 돌렸을 때 모두 돌아가서 이렇게 글을 남깁니다

제가 구현한 코드는

1.마지막 계단을 밟아야해서 내려오는 식으로 점수를 구했습니다

2.이전의 계단이 2개단 연속인 conti = true상태이면 전전계단과의 합을 구하고

그렇지 않다면 전전계단과 전계단을 비교해서 지금의 계단에 더해주었습니다.

다른 분들보면 다르게 구현했던데 제가 구현한 방식자체가 문제인가요?

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {	
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		int[] step = new int[N];
		Step[] dp = new Step[N+1];
		
		for(int i = 0; i < N; i++) {
			step[i] = Integer.parseInt(in.readLine());
			dp[i] = new Step();
		}
		
		for(int i = N-1; i >= 0; i--) {	
			if(i == N-1) dp[i].score = step[i];
			else if(i == N-2) {
				dp[i].score += dp[i+1].score + step[i];
				dp[i].conti = true;
			}else {
				if(dp[i+1].conti) { //이전의 계단이 전전계단을 밟은 경우
					dp[i].score += dp[i+2].score + step[i];
					dp[i].conti = false;
				}else {
					if(dp[i+2].score > dp[i+1].score) {    
						dp[i].score += dp[i+2].score + step[i];
						dp[i].conti = false;
					}else {
						dp[i].score += dp[i+1].score + step[i];
						dp[i].conti = true;
					}
				}
			}
		}
		//for(int i = 0; i < N; i++)System.out.print(dp[i].score + " ");
//		System.out.println("");
		if(N == 1) {
			System.out.println(dp[0].score);
			return;
		}else {
			System.out.println(Math.max(dp[0].score, dp[1].score));
		}
	}
}
class Step{
	int score;
	boolean conti;
}

pichulia 4년 전 1

음...어디를 어떻게 설명드려야 이해하실지 잘 모르겠어서

아래와 같은 예제를 선물로 드리겠습니다.

직접 돌려보면서 어떤 경우가 문제인지 생각해보시길 바랍니다.

quf9484 4년 전 0

알고리즘에 문제가 있다고 판단하여 새로 구현하겠습니다

감사합니다

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

문제

문제

출처

ICPC

2579 계단오르기 도저히 모르겠습니다.

quf9484 4년 전 0

pichulia 4년 전 1

quf9484 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말