완전탐색

드디어 이해완... 확실히 1208번 풀고 다시 보내까 이해가 수월하다.

이 문제를 접근하기 어려웠던 이유는, "회전","낙차"라는 키워드에서 겁나 쫄았기 때문.

일단 이러한 배열 문제가 나오면 거의 다 완탐이라고 생각하면 된다.

당황하지 말고 행과 열, 둘 중 어떤 것으로 접근하여 코드를 짤 지 결정해야한다.

그림은 복잡해보이지만 , 잘 보면 이 문제에서는 행이 중요하다.

0번째 행에는 블록이 0개, 1번째 행에는 블록이 2개, 2번째 행에는 블록이 3개...

그리고 최종적으로 낙하를 시키면, 낙차는 배열의 총 길이(num) - 각 행의 블록 개수가 된다.

if 문으로 반복 돌리고, 최댓값만 비교해주면 바로 답이 나온다.

이렇게 생각하믄 얼마나 쉽냐고!!! 혼자 더 복잡하게 생각하고 난리였다. 

 

package week_FOUR;
import java.util.*;
/*
 * 이해완!!!!
 * 완전 탐색 문제다... 
 * 일단 배열 자체를 회전한다고해서 쫄지마셈... 
 * 행으로 생각할건지 열로 생각할건지부터 정하셈.
 * 그림 보면  
 */
public class Nakha_Final {
    
    public static void GetAnswer(int n, int arr[]) {
        int max = 0;
        
        for (int i = 0; i < n; i++) {
            int Nakcha = n - 1 - i;
            int now = arr[i];
        //상자가 있는 바로 다음 행(가로)부터 탐색 시작
        for (int k = i +1 ; k<n ; k++) {
            if(now < arr[k]) Nakcha--;
        }
        if (max < Nakcha) max = Nakcha;
    }
    System.out.println(max);
}
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int arr[] = new int[num];
        for (int i = 0; i<num; i++) {
            arr[i] = sc.nextInt();
        }
        
        GetAnswer(num, arr);
 
    }
 
}