[IT/코딩테스트] 자율 코테 스터디<평일> TIL + BOJ2212

 

 

오늘의 문제

https://www.acmicpc.net/problem/2212

골드5

 

오늘 항해 코테 문제는 이미 풀고 업로드 완료!

생각보다 일찍 끝나서 다른 카테고리의 문제도 풀어보았다.

 

저번 스터디 때, 그리디에 대해서 알려주셨는데.. 다음주 문제들이 그리디라서 살짝 아쉬웠기에!

추가 문제로 그리디를 풀어보았다.

 

그런데 사실 왜 그리디인지는 모르겠고 그냥 정렬하다가 끝났다 ... 🙃

 

---

나의 첫 번째(?) 풀이 (성공)

아래는 문제를 어떻게 풀 것인가에 대해서 생각한 흐름

 

** 생각의 흐름

1) 우선 직선 위에 센서들이 있다고 했으니, 위치를 정렬 하자

2) 위치 사이의 거리를 구해서 저장해두자

3) 만약에 집중국이 센서수 만큼 있거나 더 많으면 거리가 생길 이유가 없다. 0이니까.

4) 거리도 정렬을 시켜서 큰 수를 기준으로 센서수 만큼 그룹으로 나누어지도록 하자.

5) 큰 거리순으로 제거하고 남은 거리의 합을 구하자.

 

그렇게 작성한 코드를 파이참에서 실행해보았고, 올바르게 동작하는 것을 확인한 후에 백준 사이트에 입력했다.

그리고 결과는 ..... 

 

 

 

사실 print 문을 if-else 문 안에 넣었어야 했는데 밖에 작성했다가 런타임 에러가 났다 ㅋㅋㅋ

뭐지??? 싶어서 확인했고 바로 위치 조정해서 해결👍

 

아래는 작성한 전체 코드!!

 

import sys

n = int(sys.stdin.readline()) # 센서 수
k = int(sys.stdin.readline()) # 집중국 수
way = sorted(list(map(int, sys.stdin.readline().split())))
distance = []

if k >= n:
    print(0)
else:
    for i in range(n-1):
        d = way[i+1]-way[i]
        distance.append(d)
    result = sorted(distance, reverse=True)
    for _ in range(k-1):
        result.pop(0)
    print(sum(result))

 

 

해피해피해피🤭

내일도 문제 하나 + 추가 문제 풀어서 복습하자!