<Algorithm> 177. 자기방으로 돌아가기(SWExpert)

자기방으로 돌아가기(SWExpert)

   사용 알고리즘 :  누적

• 문제는 간단했지만 상당히 어려웠던 문제... D4난이도에 걸맞지 않은 것 같다.(코드가 간단하기만 하면 D4 주는듯..)
• 힌트를 보고 풀었는데 어떻게 이런 사고가 가능한지 신기했다. 

문제에 대한 접근&생각

1. 방을 옮길때 겹치면 시간이 늘어남 -> 결과조건!
2. 마주보는 방은 같은 복도를 사용함 -> 하나의 방으로 설정!
3. 지나갈때마다 겹치는 구간이 존재함 -> 모든 이동경로를 카운트!
4. 겹치는 구간 중 가장 많은 곳 발생 -> 가장 많이 겹치는 구간이 최솟값!

내 코드 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

import java.util.Scanner;   public class Solution {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int test = sc.nextInt();         /****************************          * 마주보는 방을 같은 번호로 맞추고          * 옮길때마다 누적하여 가장 큰수를          * 출력한다.          ****************************/         for(int t = 1; t<=test;t++) {             int n = sc.nextInt();             int rooms[] = new int[201];             int max = 0;             for(int i = 0; i < n; i++) {                 int room1 = sc.nextInt();                 int room2 = sc.nextInt();                 if(room1 > room2) {                     int temp = room1;                     room1 = room2;                     room2 = temp;                 }                 if(room1%2 != 0)room1++;                 if(room2%2 != 0)room2++;                 room1 = room1/2;                 room2 = room2/2;                 for(int move = room1; move<=room2; move++)                     rooms[move]++;                 for(int k = 0; k < rooms.length; k++)                     max = Math.max(max, rooms[k]);             }             System.out.println("#"+t+" "+max);         }     } }   Colored by Color Scripter

cs