[Java] 참외밭 [2477번]

https://www.acmicpc.net/problem/2477

• 예제 입력1

7
4 50
2 160
3 30
1 60
3 20
1 100

• 예제 출력1

47600

---

• 문제 접근
  • 직사각형의 넓이(6050=8000)에서 제외할 직사각형의 넓이(6020)를 빼야 함
  • 임의의 꼭지점에서 역시계 방향으로 진행이 되기 때문에 아래의 규칙을 항상 만족
• 문제 해결
  • 방향과 길이를 저장한 배열을 각각 생성
  • 길이가 가장 긴 가로 길이, 인덱스 / 길이가 가장 긴 세로 길이, 인덱스 저장
  • 꼭지점을 기준으로 항상 역방향이기 때문에 다음과 같은 규칙 생성
    • 제외할 사각형의 가로 길이 ⇒ 가장 길이가 긴 가로에서 4번 뒤에 등장
    • 제외할 사각형의 세로 길이 ⇒ 가장 길이가 긴 세로에서 2번 뒤에 등장

• 슈도 코드

K (참외 개수 저장)
direction[] (방향 배열 선언)
length[] (길이 배열 선언)


for(6회 반복){
	direction[] (방향 저장)
	length[] (길이 저장)
}

maxX(가장 긴 가로), maxX_idx(가장 긴 가로 인덱스)
maxY(가장 긴 세로), maxY_idx(가장 긴 세로 인덱스)
for(6회 반복){
	if(방향이 2이하라면){
		if(maxX보다 length[i]가 더 크면){
			maxX에 length[i] 저장
			maxX_idx에 i 저장
		}
	} else{
			if(maxY보다 length[i]가 더 크면){
				maxY에 length[i] 저장
				maxY_idx에 i 저장
			}
		}
}

exceptX(제외할 가로 길이) = length[maxX_idx + 3의 길이]
exceptY(제외할 세로 길이) = length[maxY_idx + 3의 길이]


res ((최대 가로 X 최대 세로) - (제외 가로 X 제외 세로)) * K 저장
res 출력

• 코딩하기

public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    int K = Integer.parseInt(br.readLine());
    int size = 6;
    int[] direction = new int[size];
    int[] length = new int[size];
    for(int i = 0; i < size; i++){
        st = new StringTokenizer(br.readLine());
        direction[i] = Integer.parseInt(st.nextToken());
        length[i] = Integer.parseInt(st.nextToken());
    }
    br.close();
    int maxX = 0, maxX_idx = 0;
    int maxY = 0, maxY_idx = 0;
    for(int i = 0; i < size; i++){
        if(direction[i] <= 2){ // 방향이 1 or 2일 경우(가로)
            if(maxX < length[i]){
                maxX = length[i];
                maxX_idx = i;
            }
        }else {
            if(maxY < length[i]){ // 방향이 3 or 4일 경우(세로)
                maxY = length[i];
                maxY_idx = i;
            }
        }
    }
    int exceptX = length[(maxX_idx+3) % size]; // 배열 범위 초과 방지
    int exceptY = length[(maxY_idx+3) % size]; // 배열 범위 초과 방지
    int res = ((maxX * maxY) - (exceptX * exceptY)) * K;
    System.out.println(res);
}