[Baekjoon] 3621/족보/Python/파이썬/그리디 알고리즘

💡문제

외계인 피터는 그의 족보를 추적하려고 한다. 피터는 몇 주동안 열심히 작업해 족보의 베타 버젼을 만들었다.

족보를 살펴보니 선조 중 일부가 너무 많은 부모를 가졌다는 사실을 알게되었다. (외계인 d명의 부모를 가진다) 그래서 피터는 몇몇 부모-자식 관계는 선조-자손 관계일 것이라고 생각했다.

피터가 족보를 만족스러운 형태로 바꾸려면 최소 몇 명을 추가해야 하는지 구하는 프로그램을 작성하시오.

각각의 외계인의 부모의 수가 d명을 넘지 않고, 각 외계인이 족보에 한 번만 노출된 경우에 만족스러운 형태라고 한다.

예를 들어, d가 2이고 피터가 만든 족보의 베타 버젼이 아래와 같다면,

아래와 같이 선조 두 명을 추가하면 만족스러운 형태가 된다.

입력

첫째 줄에 두 정수 n과 d가 주어진다. (2 ≤ n ≤ 100,000, 2 ≤ d ≤ n) 다음 줄에는 총 n개의 정수가 주어지며, i번째 정수는 i번째 자식의 번호이다.

피터의 족보에 등장하는 선조는 모두 1번부터 n번까지 번호로 나타낸다. 피터의 번호는 0번이다.

출력

족보를 만족스러운 형태로 바꾸기 위해서 최소 몇 명을 추가하면 되는지 출력한다.

예제입력

6 2
5 5 0 5 0 5

예제출력

2

---

📖내가 작성한 Code

import sys
import math


def add_parents(d,parent_counts):
    parent = 0
    for i in parent_counts:
        if i > d:
            parent += math.ceil((i - d) / (d - 1))
    return parent


def main():
    inputs = map(int,sys.stdin.read().split())
    n,d = next(inputs),next(inputs)
    parent_counts = [0]*(n+1)

    for _ in range(n):
        parent_counts[next(inputs)] += 1

    sys.stdout.write(str(add_parents(d,parent_counts)))


if __name__ == "__main__":
    main()

---

✍️풀이과정

그냥 손으로 그려보면 됨. 나는 부모가 5명인데 d가 4. 부모가 14명인데 d가 4. 이렇게 두 개 해보고 알게 되었음. 이런 수학류 문제는 센스가 중요한듯.

바로~ 1등.

---

🧠 코드 리뷰

1. 입력 처리 개선: 현재 코드는 map(int,sys.stdin.read().split())을 사용하여 입력을 처리하고 있습니다. 이 방법은 전체 입력을 메모리에 로드하므로, 입력 데이터가 매우 클 경우 메모리 사용량이 증가할 수 있습니다. 대신, sys.stdin을 직접 순회하여 필요한 부분만 처리하는 것이 메모리 효율성 측면에서 유리할 수 있습니다.

---

🛠️AI 개선 코드

import sys
import math

def calculate_additional_parents(d, parent_counts):
    additional_parents = 0
    for count in parent_counts:
        if count > d:
            additional_parents += math.ceil((count - d) / (d - 1))
    return additional_parents

def main():
    input = sys.stdin.read().split()
    n = int(input[0])
    d = int(input[1])
    parent_counts = [0] * (n + 1)

    for i in range(2, 2 + n):
        parent_counts[int(input[i])] += 1

    print(calculate_additional_parents(d, parent_counts))

if __name__ == "__main__":
    main()

---

💻결과

백준문제 보러가기

---

🖱️참고 링크

나무위키 그리디 알고리즘 참고