[Softeer/소프티어][Level3]징검다리(Java)

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=391 

Softeer

[문제]

남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다.

 

이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다. 철수는 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟으면서 개울을 지나가려고 한다.

 

돌의 높이가 서쪽의 돌부터 동쪽방향으로 주어졌을 때 철수가 밟을 수 있는 돌의 최대 개수는?

 

[풀이]

import java.util.*;
import java.io.*;


public class Main
{	
	
	static int N;
	static int[] A, ROCKS;
	static int COUNT;
	static int MAX;
	
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		A = new int[N];
		ROCKS = new int[N];
		COUNT = 0;
		MAX = -1;
		
		for (int i = 0; i < N; i++)
		{
			A[i] = sc.nextInt();
			ROCKS[i] = 1;
		}
		
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j <= i; j++)
			{
				if (A[j] < A[i])
					ROCKS[i] = Math.max(ROCKS[i], ROCKS[j] + 1);
			}
		}
		
		for (int i = 0; i < N; i++)
		{
			if (MAX < ROCKS[i])
				MAX = ROCKS[i];
		}
		
		System.out.println(MAX);
		
		sc.close();
	}

}