[코드트리/NOVICE MID] 원 모양으로 되어있는 방 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
        
        int[] arr = new int[N];
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
 
        // 시작점 돌아가면서 설정해보고, 그 중 최솟값 구해보기
        int min = Integer.MAX_VALUE;
        for(int i = 0 ; i < N ; i++) {
            int tmp = 0;
 
            for(int j = 0 ; j < N ; j++) {
                if(j == i)    continue;
 
                if(j >= i) {
                    tmp += (j - i) * arr[j];
                }
                else {
                    tmp += (arr.length - i + j) * arr[j];
                }
            }
            //System.out.println(tmp);
            min = Math.min(min, tmp);
        }
 
        System.out.println(min);
 
    }
}

 

 

 

🧩  해결 아이디어

• 완전탐색

- 시작점을 돌아가면서 설정해보고, 그 중 최솟값을 구한다.

 

- 만약 현재 위치 j가 시작점으로 설정한 방 i와 같다면, pass한다.

- 그게 아니라면, 이동 거리에 인원 수를 곱한 값을 더하며 총 거리의 합을 구한다.

└ j가 i보다 크거나 같은 경우, 단순히 (j - i)만큼이 이동 거리다.

└ j가 i보다 작은 경우, 방의 개수에서 시작점 방 위치까지 빼 거리를 구하고, 현재 방의 위치 인덱스를 더해 총 거리를 구한다.

여기에 인원수룰 곱한다.

 

- 총 거리의 합과 최소값을 비교해 최소값을 갱신한다.

 

 

 

---

🔺 다른 풀이들

- 거리를 구할 때 이렇게 한 번에 구해도 된당....

int dist = (j + arr.length - i) % n;

 

---

💬 느낀 점

어려운 문제가 아닌데.

담엔 빠르게 풀자...

 

 

1회독	2회독	3회독	4회독	5회독
V