[백준] 10800 컬러볼

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

공의 색이 최대 200,000 개가 나올 수 있으므로 단순 이중 반복문으로 풀이시 시간초과 문제가 발생할것을 예상하였습니다.

1차적으로 공의 크기별로 정렬을 하였고 크기가 작은 순서대로 확인하며 누적합을 쌓는 방법을 이용하였습니다.

그러나 사이즈가 같은 공이 여러개 나오는 경우, 다음 순서 진행시 누적합에 같은 사이즈의 합도 포함이 되는 오류가 발생하였습니다.

이러한 문제 해결을 위해 같은 사이즈 발견시 처리해주는 코드를 작성하였습니다.

2) 알고리즘

• 누적합

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

N = int(sys.stdin.readline())                           # 공의 개수
infos = []                                              # 공의 정보들
answers = {}                                            # 정답 변수

for idx in range(N):                                    # 공의 정보들 저장
    C, S = map(int, sys.stdin.readline().split())
    infos.append((C, S))

sorted_size = sorted(infos, key=lambda x: (x[1], x[0])) # 공을 사이즈별로, 색상별로 정렬

pre_size = 0                                # 이전 경우의 공의 사이즈
pre_color = 0                               # 이전 경우의 공의 색상
pre_idx = 0                                 # 이전 경우에서 현재 경우보다 작은 사이즈의 인덱스

acc_sum = [[0] for _ in range(N+1)]         # 0번 인덱스 - 공의 사이즈 누적합, 1번 인덱스 이후 - 공의 색상별 누적합
for i in range(N):
    c, s = sorted_size[i]               
    acc_sum[0].append(acc_sum[0][-1] + s)   # 공의 사이즈 누적합
    acc_sum[c].append(acc_sum[c][-1] + s)   # 공의 색상별 사이즈 누적합

    if pre_size == s:                                                   # 이전과 같은 사이즈 공이면
        if pre_color != c:                                              # 이전과 다른 색상일때, (정답은 딕셔너리 변수이므로 같은 색, 같은 사이즈는 한번만 저장하면 됨)
            answers[(c, s)] = acc_sum[0][pre_idx] - acc_sum[c][-1]      # 나보다 작은 사이즈까지의 누적합 - 나와 같은 색상들 누적합 (두 경우에 나의 사이즈 합도 모두 포함되어 있음)
    else:
        answers[(c, s)] = acc_sum[0][-1] - acc_sum[c][-1]               # 사이즈 누적합 - 나와 같은 색상들 누적합
        pre_idx = i + 1                                                 # 사이즈 누적합 인덱스 변경

    pre_size = s                            # 이전 경우의 사이즈와 색상 변경
    pre_color = c


for c, s in infos:
    print(answers[(c, s)])

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

같은 사이즈로 인하여 오류 발생시 조건을 추가하여 처리를 하였으나, 시간초과 문제가 발생하였습니다.

시간 초과 문제 해결을 위하여 변수 사용을 줄이게 되었을때, 또 다른 오류들이 발생하였습니다.

(1) 참고 사이트

• 블로그
  같은 사이즈와 같은 색상이 나타났을때 처리하는 조건을 참고하였습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

- https://www.acmicpc.net/problem/10800

10800번: 컬러볼

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다