🔔문제 소개

---

🔗연습 요약

연습 시간	연습 문제 수	카테고리
100 분	6 문제	그리디, 다이나믹 프로그래밍, 정렬, 그래프 이론 중 랜덤 3 선택

🔗문제 요약

문제	번호	난이도	시간 내 풀이 여부	풀이 여부
양동이 게임	28360	S1		바로가기
나는 위대한 슈퍼스타K	2865	S4	O	O
1, 2, 3 더하기 9	16195	S1		바로가기
튜터-튜티 관계의 수	24542	S1		바로가기
병사 배치하기	18353	S2	O	O
양팔저울	25943	S4	O	O

📑풀이 노트

---

📌나는 위대한 슈퍼스타 K

문제 요약

참가자의 수와 장르가 주어지고, 장르마다 각 참가자의 능력을 실수형 데이터로 나타냈다.
각 참가자는 하나의 장르만 부를 수 있으며, 한 장르는 여러 참가자들에 의해 불려질 수 있다.
이떄 능력의 합이 최대가 되도록 참가자와 장르를 선택해라.

풀이 요약

풀이 순서	풀이 시간	시도횟수	카테고리
1	H+73	3	그리디, 정렬

맨 처음에 문제가 이해가 잘 가지 않았는데, 곰곰히 생각해보니 단순히 정렬한 뒤에 높은 순서대로 K만큼만 더하면 된다라는 아이디어에 도달하였다.

코드

n,m,k = map(int, input().split())
info = {i:[] for i in range(1, n+1)}
for i in range(m):
  genre = input().split()
  for j in range(0, (n*2), 2):
      kk, v = genre[j:j+2]
      info[int(kk)].append(float(v))

s = []
for v in info.values():
  s.append(max(v))
s.sort(reverse=True)
print(round(sum(s[:k]), 1))

회고

소수점 첫째자리에서 반올림 해야 한다는 조건을 구현 하지 않았었다. 쉬운 문제였는데 쓸데없이 시간을 많이 쓴 문제. 입력형태도 까다로웠다고 느꼈음. 앞으로는 주의하자.

📌병사 배치하기

문제 요약

N명의 병사가 무작위로 나열되어있고, 각 병사마다 특정한 전투력을 가지고있다.
이때 몇명의 병사를 열외시켜 전투력을 내림차순으로 정렬하고싶다.
이때 열외하는 병사를 최소로 한다면 몇명을 열외시켜야 하는가?

풀이 요약

풀이 순서	풀이 시간	시도횟수	카테고리
2	H+79	2	다이나믹 프로그래밍

문제를 조금 바꿔보면, 전투력을 기준으로한 가장 긴 부분 증가 수열 문제였다, 내가 구하고 싶은건 단순히 길이이므로, bisect를 이용해 풀이하였고, LIS를 구한 뒤 전체에서 빼주면 내가 원하는 열외자의 수를 구할 수 있다.

코드

from bisect import bisect_left
n = int(input())
s = list(reversed(list(map(int, input().split()))))
lis = [int(1e9)]

for i in s:
  if i > lis[-1]:
      lis.append(i)
  else:
      lis[bisect_left(lis, i)] = i

print(n- len(lis))

회고

처음에는 그리디와 다이나믹 프로그래밍 사이에서 긴가민가했다. 빠르게 내가 원하는 코드를 작성할 수 있었고, 아이디어를 떠올릴 수 있었던것이 좋았던 문제이다. 풀이시간도 6분으로 만족스러웠다.

📌양팔저울

문제 요약

아래 조건에 따라 자갈을 배치하고, 무게추를 이용해 평형을 맞출때 무게추의 개수를 최소로 하는 개수를 구해라
조건

1. $1$번 자갈을 왼쪽,
2. $2$번 자갈을 오른쪽에 올려놓는다.

$i = 3, \dots , n$번 자갈 각각에 대해서 차례로 다음 과정 중 하나를 수행한다.

1. 만약 양팔저울이 평형을 이루는 경우,
   $i$번 자갈을 왼쪽에 올려 놓는다.
   
   
2. 만약 양팔저울이 평형을 이루지 않는 경우,
   $i$번 자갈을 가벼운 쪽에 올려 놓는다.
   

풀이 요약

풀이 순서	풀이 시간	시도횟수	카테고리
3	H+87	3	구현, 그리디

아이디어 및 코드

k = int(input())
stone = list(map(int, input().split()))
left, right = [stone[0]], [stone[1]]
for i in  stone[2:]:
  if sum(left) == sum(right):
      left.append(i)
  else:
      if sum(left) > sum(right):
          right.append(i)
      else:
          left.append(i)

between = abs(sum(left) - sum(right))
weight = [100, 50, 20, 10, 5, 2, 1]
w = 0
cnt = 0
while between:
  if weight[w] <= between:
      between -= weight[w]
      cnt += 1
  else:
      w += 1
print(cnt)

회고

단순 구현문제에 그리디를 그냥 끼워넣은 느낌이라 크게 어렵지 않게 문제를 따라가며 풀이한 문제.
시간을 조금 더 이 문제에 썼다면 while문 안을 조금 더 최적화 할 수 있는 방법이 있었는데 제한시간에 걸리지 않을것 같아 쌩 탐색을 하였다. 예를들면 한번에 큰 수를 여러개 빼는 방법이 있었을 것이다. (% 연산 이용)

전체 회고

---

첫 테스트로 실버 문제 위주의 선택을 했는데 다음 연습부터는 실버 3이상의 실버 문제들로만 구성한 뒤 문제를 풀어봐야겠다. 쓸데없는데에서 시간낭비를 줄이고, 예상과 다른 결과를 낸다고 조급해하지 말자.