글 읽기 - 아무리 생각해도 이게 왜틀렸죠 파이썬입니다

kje7584 3년 전 0

제가 왜 틀렸는지 모르겠습니다. 0프로에서 틀렸다는 데 반례나 논리적 이유가 있을까요..?

import collections
import sys

sys.setrecursionlimit(10 ** 4)
input = sys.stdin.readline


def iinput(): return int(input())


def lisinput(): return list(map(int, input().split()))



def minput(): return map(int, input().split())




def findParent(arr, n):
    if arr[n] == n:
        return n
    else:
        arr[n] = findParent(arr, arr[n])
        return arr[n]


def unionParent(arr, a, b):
    pa = findParent(arr, a)
    pb = findParent(arr, b)
    if pa < pb:
        arr[pb] = pa
    else:
        arr[pa] = pb
    return min(pa, pb)


if __name__ == '__main__':
    n = iinput()
    maps = []
    hh = []
    arr = [i for i in range(n)]
    for i in range(n):
        a, b = minput()
        maps.append([a, b])
        if i != 0:
            hh.append([-a, i, maps[i - 1][0], maps[i][1]])
            # heapq.heappush(hh, [-a, i])  # 나와 이 이전을 고려
    hh = sorted(hh, key=lambda x: (x[0], x[2] * x[3]))
    answer = 0
    for travel in hh:
        beforeMom = findParent(arr, travel[1] - 1)
        afterMom = findParent(arr, travel[1])
        if beforeMom == travel[1] - 1 and afterMom == travel[1]:
            arr[travel[1]] = travel[1] - 1
            answer += maps[travel[1] - 1][0] * maps[travel[1] - 1][1] * maps[travel[1]][1]
        elif beforeMom != travel[1] - 1 and afterMom == travel[1]:
            arr[travel[1]] = findParent(arr, travel[1] - 1)
            lastParam = travel[1]
            for k in range(travel[1] + 1, n):
                if arr[k] == travel[1]:
                    lastParam = k
                    arr[k] = arr[travel[1]]
                else:
                    break

            answer += maps[findParent(arr, travel[1] - 1)][0] * maps[lastParam][1] * maps[travel[1]][0]
    print(answer)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

아무리 생각해도 이게 왜틀렸죠 파이썬입니다

kje7584 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말