[코드트리] 원 모양으로 되어있는 방 / 완전탐색

 

https://www.codetree.ai/missions/5/problems/a-room-in-a-circle?&utm_source=clipboard&utm_medium=text 

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

 

 

 

원 모양으로 되어있는 방

---

 

 

원 모양으로 되어있는 N개의 방이 있고, 방은 1부터 N까지 시계 반대방향으로 번호가 매겨져 있습니다. 각 방에는 이웃한 두 개의 방으로 통하는 문이있습니다. 사람들은 무조건 시계 반대방향으로만 이동해야 합니다. 각자 방에 몇 명이 사람이 들어가야하는지 주어지며, 모든 사람이 같은 방에서 시작한다고 합니다. 어떤 방에서 시작해야 각 방에 정해진 인원이 들어가는 데까지의 거리의 합을 최소화 할 수 있는지를 계산하는 프로그램을 작성해보세요.

 

 

입출력 예제

 

예제1

입력:

 

5
4
7
8
6
4

 

출력:

48

 

 

원 모양으로 된 방이 N 개 존재한다. 이 N개의 방에는 사람이 각각 방에 해당하는 사람 수가 들어가야한다. 모든 사람들은 첫번째 시작하는 방에 모여있다고 가정한다. 위 예시에서는 5개의 방이 있다. 

1번 방은 4명, 2번 방은 7명 , 3번 방은 8명, 4번방은 6명, 5번방은 4명이 가야한다.

그런데 이 모든 인원이 처음 시작하는 방에 존재하고 반시계 방향으로 방을 이동하며 해당하는 인원 수만큼 방에다 놓고 이동한다고 생각한다. 그리고 이 모든 사람의 이동거리를 구한 후 이동 거리가 최소가 되도록 해야한다.

 

이 예시에서는 만약 2번 방에서 출발한다고 가정하자. 2번방에 들어가야하는 7명은 이동하지 않고 남는다. 반시계방향으로 이동해야하므로 3번방에 간다. 3번방에는 8명이 가야한다. 따라서 {8명*이동한 거리인 1 = 8 }로 현재 총 거리는 8이다.

이 8명이 내린 후 4번 방으로 이동한다. 4번방에는 6명이 내려야한다. 6명은 2번방에서 시작해서 2개의 방을 지났다. 따라서 6명이 이동한 거리는 {6명*이동한 거리인 2=12} 이므로 현재 총 거리는 8+12 = 20이다.

5번방으로 이동한다. 5번방에는 4명이 나가야한다. {4명*이동거리3=12}이르모 현재 총거리는 20+12 = 32 이다.

다음은 끝났다.

가 아니라 1번방이 남아있다. 이 방들은 원으로 이어져있다는 것을 있지말자. 

1번방에는 4명이 가야한다. 따라서 {4명*이동거리 4=16}이므로 현재 총거리는 32+16 = 48이다.

 

여기서는 이 48이 최소거리가 된다. 이러한 탐색을 1번방에서 출발한다 가정, 2번방에서 출발한다 가정, .. , N번방에서 출발한다 가정하고 모든 거리를 비교해보고 최소거리를 출력해야한다.

 

 

 

 

 

 

코드

import sys


N = int(input())
ans = sys.maxsize

rooms = [
    int(input())
    for _ in range(N)
]

for i in range(N):
    dist = 0
    # i 는 시작 방 위치를 나타냄
    for j in range(i, i + N):
        room_idx = j % N
        dist = dist +  rooms[room_idx] * abs(j-i)
    ans = min(ans, dist)


print(ans)

우선 sys 모듈을 임포트한 후 maxsize() 메소드로 맥스값을 ans 에 초기화시킨다. 우리는 지금 최솟값을 구해야하기 때문에 영향을 주지 않으려 맥스값을 넣는 것이다. 그리고 방의 개수를 입력받고 각 방마다 내려야하는 사람수를 배열로 입력받는다.

 

for i in range(N):

으로 N개의 방에 대해서 하나씩 돌아가며 출발위치를 정한다.

다음은 거리를 계산해야하는데

방향은 반시계 방향으로 정해져있으므로 

i 부터 반복한다. 주의할 점은 방의 개수만큼 돌아야한다는 점이다.

만약 2번방에서 출발했어도 1번방을 들려야한다. 

따라서 i+N 까지 순회해야한다.

 

for j in range(i, i+N):

그리고 인덱스에 주의해야한다.

방의 인덱스번호는 초기에 설정한 N-1까지만 가능하고 N이상이 되면 오류가 뜬다. 따라서 

j%N 을 통해 N 으로 나눴을때의 나머지가 방의 인덱스 번호가 되게 하여 정해진 범위를 넘지 않도록 해주었다. 

 

거리에 현재 룸의 수용 인원 * 이동거리를 곱해야하므로

dist = dist + rooms[i] * abs(j-i)

를 통해 구한다. 이 dist 가 최소가 되는 출발 위치를 정하면된다.