우주의 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

이 문제를 보자마자, 아 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")

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

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

안녕하세요. 오늘은 백준 알고리즘 1966번 프린터 큐를 풀어보았습니다.

먼저 입/출력을 받을 변수와 대략적인 코드 진행의 가이드라인을 그려보겠습니다.

입력 : 테스트케이스의 수, 문서의 개수, 원하는 문서의 인덱스, 중요도

출력 : 원하는 문서의 인쇄 순서

대략 2~3가지의 해결 방법이 떠오르는데, 이번 풀이에서는 우선순위를 리스트에 저장 해두었다가

중요도를 비교하여 제일 높은 중요도일 경우 추가하고, 아닐 경우 맨 뒤로 보내는 방법으로 풀이해보겠습니다.

priority 리스트에 우선순위를 입력하고

queue 덱에 원하는 문서의 인덱스, 그 문서의 우선순위를 튜플로 삽입합니다.

그 뒤 반복을 통해 현재 큐의 우선순위가 제일 높은 우선순위일 경우:

우선순위 리스트 priority에서 현재 우선순위를 제거해줍니다.

현재 큐의 우선순위가 제일 높은 우선순위가 아닐 경우:

queue의 맨 뒤에 현재 큐를 추가하고

현재 큐를 삭제시켜줍니다.

이렇게 priority가 빌 때 까지 연산을 반복하면 원하는 결과가 정렬되겠습니다.

그 후 queue에서 원하는 인덱스를 찾아 출력해주면 끝입니다.

<풀이 코드>

from collections import deque
import sys
loop = int(sys.stdin.readline())
for _ in range(loop):
    doc_count, index = map(int, sys.stdin.readline().split())
    priority = list(map(int, sys.stdin.readline().split()))
    queue = deque([(i, priority[i])for i in range(doc_count)])

    idx = 0
    while idx < doc_count:
        if queue[idx][1] == max(priority):
            priority.remove(queue[idx][1])
            idx += 1
        else:
            queue.append(queue[idx])
            queue.remove(queue[idx])

    for i in range(doc_count):
        if queue[i][0] == index:
            print(i + 1)
            break

What does not destroy me, makes me stronger. - Friedrich Nietzsche

아직 모자라지만, 항상 배우고, 나아가려합니다.

오타 / 오류 / 개선점 / 질문 환영합니다 ^^