우주의 IT 소행성

기본적인 수학 공식을 사용하면 바로 풀리는 문제였다.

l, p, v가 주어졌을 때, (v // p) * l에서 대부분이 정해지고

남은 일자가 l보다 크다 작다에 따라서 상세값이 정해진다.

따라서 v - (v // p) * p < l 일 경우 위 값에 더해주면 되고

아닐 경우 l을 더해주면 된다.

count = 1
while True:
    l, p, v = map(int, input().split())
    if l == p == v == 0:
        break
    result = (v // p) * l
    if v - (v // p) * p < l:
        result += v - (v // p) * p
    else:
        result += l

    print("Case %d:" %count, result)
    count += 1

테스트 케이스가 많다보니 sys로 input = sys.stdin.readline 해주지 않으면 시간 초과가 발생했다.

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    data = []
    count = 1
    for _ in range(n):
        data.append(list(map(int, input().split())))
    data.sort()

    tmp = data[0][1]

    for i in range(1, n):
        if tmp > data[i][1]:
            count += 1
            tmp = data[i][1]
    print(count)

서류와 면접중 한 점수를 기준으로 오름차순 정렬을 한 뒤

총 5명의 지원자 일 경우 

서류 점수가 1등인 자의 면접 점수가 4일 경우

면접점수가 4보다 아래인 사람은 자동으로 탈락이다.

이런식으로 반복을 더해나가며 문제를 해결했다.

물론 처음부터 문제를 해결할 수 있었던건 아니였다.

for _ in range(int(input())):
    n = int(input())
    data = []
    count = 0
    for _ in range(n):
        data.append(list(map(int, input().split())))
    data.sort()
    data2 = sorted(data, key= lambda x : x[1])

    result = []
    for i in range(data[0][1] + 1, n + 1):
        result.append(i)

    for i in range(data2[0][0] + 1, n + 1):
        result.append(data[i - 1][1])


    print(n - len(set(result)))

원래는 서류 점수 1등의 면접 점수를 기준으로 그보다 낮은 요소들을

list의 del을 이용해서 제거한 뒤, 남은 인원들의 인원수를 len(data)를 통해 정답을 구하려 했으나

len(data)의 변화를 for 문에서는 초기 len(data)의 값으로만 고정이 된다는 점을 착각하여 index out error가 발생하였다.

그래서 리스트를 서류 기준 / 면접 기준으로 2개로 나누어 풀어보았지만, 역시 시간초과가 발생하였다.

문제를 단순히 보고 직관적으로 해결할 수 있어야 하는데, 자꾸 스스로 어려운 방향으로 나아가는 것 같다.

그래도 솔직히 정형화 된 방법보단, 즉흥적으로 떠오르는 방법으로 딱 풀었을 때 그 손맛이 계속 코드를 두들기게 하는 것 같다.

하지만 내 실력이 쌓일 때 까지는 문제를 파악하고 정확한 해결법을 연상시켜 풀이할 수 있는 PS능력을 기르자!

이 문제를 보자마자, 아 permutation을 써서 나올 수 있는 모든 경우의 수중 30으로 나누어 떨어지는 수의

최대 값이 정답이겠구나! 라는 생각이 들어 코드를 짜보았으나.. 결과는 시간초과였다.

from itertools import permutations
n = input()
data = []

for i in permutations(n, len(n)):
    tmp = int("".join(i))
    if tmp % 30 == 0:
        data.append(tmp)

if data:
    print(max(data))
    exit()

print("-1")

시간 초과가 된 코드는 바로 이것인데, 순열의 경우의 수가 10^5 까지 간다면, 그만큼 시공간 복잡도의 수가 기하급수적으로 늘어나게 됨을 간과하였다.

문제를 다시 곰곰히 살펴보니, 30의 배수가 되는 가장 큰 수 를 만들라는게 제일 큰 힌트였다.

30의 배수 -> 3의 배수 이면서 10의 배수.

결국 최대 값이면서, 맨 오른쪽 끝이 0으로 끝나야하니

입력받은 값을 역순으로 정렬하여 그 값이 30으로 나누어 떨어지기만 하면 되는 것이다.

n = list(input())
n.sort(reverse = True)
n = int("".join(n))
if n % 30 == 0:
    print(n)
else:
    print("-1")

이렇게 쉽게 풀수 있었던 걸 너무 고전하였던 것 같다.

문제를 잘 읽어보는 습관을 들이자.

로프와 중량, 물리학적인 성질을 띈 문제여서 너무 어렵게만 생각했나보다.
문제에서 주어진 '최대 / 최소'를 잡아내어 그리드로 풀면  바로 풀리는 문제였다.
문제를 다각적인 시야로 보는 연습을 해야지.

n = int(input())
lopes = []
result = []

for _ in range(n):
    lopes.append(int(input()))
lopes.sort(reverse= True)


for i in range(len(lopes)):
    result.append(lopes[i] * (i + 1))

print(max(result))