백준 2846번 :: 오르막길 (Java)

문제 설명

백준 2846번: 오르막길 (Bronze 2)

상근이는 자전거를 타고 등교한다. 자전거 길은 오르막길, 내리막길, 평지로 이루어져 있다. 상근이는 개강 첫 날 자전거를 타고 가면서 일정 거리마다 높이를 측정했다. 상근이는 가장 큰 오르막길의 크기를 구하려고 한다.

측정한 높이는 길이가 N인 수열로 나타낼 수 있다. 여기서 오르막길은 적어도 2개의 수로 이루어진 높이가 증가하는 부분 수열이다. 오르막길의 크기는 부분 수열의 첫 번째 숫자와 마지막 숫자의 차이이다.

예를 들어, 높이가 다음과 같은 길이 있다고 하자. 12 3 5 7 10 6 1 11. 이 길에는 2 개의 오르막길이 있다. 밑 줄로 표시된 부분 수열이 오르막길이다. 첫 번째 오르막길의 크기는 7이고, 두 번째 오르막길의 크기는 10이다. 높이가 12와 6인 곳은 오르막길에 속하지 않는다.

가장 큰 오르막길을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 상근이가 측정한 높이의 수이자 수열의 크기인 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수 Pi(1 ≤ Pi ≤ 1000)가 주어진다. 각 숫자는 상근이가 측정한 높이이다.

출력
첫째 줄에 가장 큰 오르막길의 크기를 출력한다. 만약 오르막길이 없는 경우에는 0을 출력한다.

문제 풀이

1. 오르막길은 높이가 증가하는 부분 수열이므로 현재 높이와 이전 높이를 비교한다.
2. 오르막길이라면 현재 위치를 마지막 숫자라고 두고 오르막길의 크기를 구해서 최댓값을 갱신한다.
3. 오르막길이 아니라면 부분 수열의 첫 번째 숫자를 현재 위치로 저장한다.
4. N개의 숫자를 모두 확인한 뒤 구해지는 '가장 큰 오르막길의 크기'를 출력한다.

소스 코드

소스 코드 링크

public static void main(String[] args) throws NumberFormatException, IOException {
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	int N = Integer.parseInt(in.readLine());
	StringTokenizer st = new StringTokenizer(in.readLine(), " ");
	int num = Integer.parseInt(st.nextToken());
	int max = 0, first = num, prev = 0;
	for (int i = 1; i < N; i++) {
		num = Integer.parseInt(st.nextToken());
		// 오르막길이 이어지면 크기 갱신
		if (prev < num) {
			max = Math.max(max, num-first);
		} else { // 새로운 오르막길 시작
			first = num;
		}
		prev = num;
	}
	System.out.println(max);
}

느낀 점

브론즈 문제라서 올릴까 말까 고민하다가 뭐 입출력도 아니니까!... 올리는 게 의미가 아예 없지는 않겠다 싶어서 올리는 풀이. 문제 풀이에 다소 장황하게 써두었는데(?) 저게 풀이이자 코드의 전부이다. 보통은 풀이 방법을 정리해서 쓰곤 하는데 정리 하고 말고 할 게 없었음.

아무튼 간단한 문제라서 금방 풀었다. 오르막길만 찾으면 되는 거라서 입력 받으면서 바로 최댓값 구하기~~~ 더 간단한 방법도 있겠지만 나는 한눈에 알아볼 수 있는 것도 중요한 사람이라서🧐 실행 시간이랑은 적당히... 타협을... 시험 대비용으로 풀었는데 시험 볼 때 도움이 되었고 간만에 왕 쉬운 문제 푸니까 좋았다😊