[백준] 1090번 체커

사용 언어 - Python3

문제 -  1090번 체커

1090번: 체커

 

정답

경우의 수 줄이는 완전 탐색 (정답 맞춘 여부 X)

아이디어 생각하기

1. 2차원 => 1차원으로 계산 가능

2차원 = 1차원 계산 + 1차원 계산

이동 횟수 = (만나려는 곳의 x좌표 - 각 체커의 x좌표) + (만나려는 곳의 y좌표 -  각 체커의 y좌표)

 

2. 우리의 집 중 한 곳에서 모이기

이동 횟수를 최소화하기 위해선, 가장 가운데 있는 좌표위치가 가장 덜 움직인다.

=> x의 범위 : 체커의 x좌표 전부

=> y의 범위 : 체커의 y좌표 전부

 

3. k번째 수는 적어도 k개의 체커가 같은 칸에 모이도록 체커를 이동해야 하는 최소 횟수이다.

n = 4인 경우, 0, 2, 3, 4 명 모이는 경우 계산

첫번째 수는 1개의 체커가 모이면 된다. = 자기자신 = 이동 필요없다

두번째 수는 가장 가까운 두개의 체커가 모이면 된다

 

n = int(input())
arr = []
x,y = [], []
answer = [-1]*n

for _ in range(n):
    a,b = map(int,input().split())
    arr.append([a,b])
    x.append(a)
    y.apend(b)

# 만날 수 있는 모든 경우의 수 = 모든 체커의 x좌표와 y좌표
for nx in x:
    for ny in y:
        # 각 체커와의 이동 횟수(거리)를 계산
        dist = []
        for ex,ey in arr:
            # x의 이동 횟수 + y의 이동 횟수
            d  = abs(ex - nx) + abs(ey - ny)
            dist.append(d)
        
        # 이동 횟수 적은 것부터 정렬
        dist.sort()
        tmp = 0
        for i in range(len(dist)):
            d = dist[i]
            tmp += d
            # 이동횟수가 작은 값부터 tmp에 더해주고, answer[i]에 입력한다.
            if answer[i] == -1:
                answer[i] = tmp
            else:
                # tmp = dist[0] + dist[1] + dist[2]
                # answer[1] = dist[0] + dist[1]
                # answer[i]는 최소 i+1개 이상의 체커와 같은 칸에 모인 경우이다.
                # # tmp와 answer[i]중 더 작은 값으로 업데이트한다.
                answer[i] = min(tmp,answer[i])
print(*answer)

 

+ 최소값 업데이트 방식

min(현재까지의 값, 비교할 값)

현재까지의 값과 새로운 값 중 비교해서 더 작은 값으로 업데이트한다.

 

+ 리스트를 원소 값만 출력하기 = (*리스트명)

 

 

레퍼런스

• 정답 깃허브

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/1090_%EC%B2%B4%EC%BB%A4.py