[Python] 백준 1090번 문제

2주만에 통과하는 알고리즘 코딩테스트 (2024년)

작성

수정됨

n = int(input())
list = [list(map(int, input().split())) for _ in range(n)]
fi_answer = [int(1e6)] * n #초기 배열 생성
x_list = []
y_list = []
for x, y in list: #후보군 리스트 생성
    x_list.append(x)
    y_list.append(y)

for x_pnt in x_list:
    for y_pnt in y_list: 
        answer = []
        for x, y in list: #입력 x, y #어느 한 점에서 입력위치로부터의 거리 최솟값 계산
            answer.append(abs(x_pnt-x) + abs(y_pnt-y)) # ex) [1,4,6,7], [0,2,3,4]
        
        answer.sort()
        distance_cost = 0 #k번째 마다 이동 비용의 최소값 계산            
        for i in range(n):
            distance_cost += answer[i] #1~k
            if fi_answer[i] > distance_cost:
                fi_answer[i] = distance_cost
print(*fi_answer)

안녕하세요! 백준 1090번 문제에 대한 질문입니다. 다음과 같이 짠 코드에서 IDE에서는 결과가 잘 나오지만, 백준 제출했을 경우 틀렸습니다만 나옵니다. 아무리 수정하고 찾아봐도 이유를 잘 모르겠어서 문의드립니다.

python 코딩-테스트 알고리즘

답변 1

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

백준 1090번 문제는 거리의 최소합을 구하는 문제로, 주어진 코드가 문제 요건을 정확히 구현하지 못한 문제가 있을 수 있습니다. 아래에 몇 가지 확인해볼 점을 안내드리겠습니다:

중복 좌표 고려: 현재 코드는 모든 “후보” x와 y 좌표 쌍을 고려하게끔 되어 있습니다. 그러나, 실질적으로 유용한 후보는 고유한 지점입니다. 중복 좌표를 제거한 집합으로 반복문을 돌리는 것이 더 효율적일 수 있습니다.
잘못된 초기화: fi_answer 리스트의 초기 값을 int(1e6)로 설정하셨지만, 이 값이 적절하지 않다면 다른 큰 값으로 변경해보세요. int(1e9) 등으로 충분히 큰 값이 필요합니다.
정렬한 배열 접근법의 최적화 부족: 각 x, y 지점에서 모든 거리의 합을 먼저 구한 후 정렬을 사용하여 비용을 갱신하는 부분에서 비효율성이 있을 수 있습니다. 이는 작동은 하지만, 특정 상황에서 비효율성을 유발할 수 있습니다.

가장 중요한 부분은 입력받은 좌표들의 모든 가능한 조합을 최적화 필요 없이 직접적으로 검토하는 대신, 중복 없이 유효한 조합만을 사용하여 접근하도록 가능한 코드를 최대한 반복문 인덱스를 줄여보는 것입니다.

아래의 질문 답변예시 링크를 참고하여 더욱 자세한 설명을 얻으실 수 있습니다:
- 완전탐색 1090번 시간초과

위에서 설명드린 점을 한 번 확인해 보시고, 여전히 문제가 있으신 경우 다음 논리를 따라 문제를 조금씩 좁혀보세요.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

mcw1415

질문자

초기값에서 1e6도 충분히 큰 값으로 아무 이상이 없을 것 같았는데 1e9로 바꾸니 바로 채점이 되었습니다! 감사합니다. 근데, 초기화에 있어서 왜 int(1e6)은 안되는건가요..!

인프런 커뮤니티 질문&답변

[Python] 백준 1090번 문제