[알고리즘] 문제 풀이 해답

점수 계산(2822번)

상근이는 퀴즈쇼의 PD이다. 이 퀴즈쇼의 참가자는 총 8개 문제를 푼다. 참가자는 각 문제를 풀고, 그 문제를 풀었을 때 얻는 점수는 문제를 풀기 시작한 시간부터 경과한 시간과 난이도로 결정한다.
문제를 풀지 못한 경우에는 0점을 받는다. 참가자의 총 점수는 가장 높은 점수 5개의 합이다.
상근이는 잠시 여자친구와 전화 통화를 하느라 참가자의 점수를 계산하지 않고 있었다. 참가자의 8개 문제 점수가 주어졌을 때, 총 점수를 구하는 프로그램을 작성하시오.

score = [int(input()) for _ in range(8)]

sum = 0
idx = []

for i in range(5):
    sum += max(score)
    a = score.index(max(score))
    idx.append(str(a+1))
    score[a] = 0

idx.sort()
print(sum)
print(' '.join(idx))

하노이탑(11729번)

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

n = int(input())
def hanoi(n, start_1, final_3, help_2):
    if n==1:
        print(start_1, final_3)
    else:
        hanoi(n-1, start_1, help_2, final_3)
        print(start_1, final_3)
        hanoi(n-1, help_2, final_3, start_1)
    return

print(2**n -1)
hanoi(n, 1, 3, 2)

카드 뽑기(5568번)

상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까?

from itertools import permutations as p

n = int(input())
k = int(input())
num = [str(input()) for _ in range(n)]

print(len(set(list(''.join(i) for i in p(num,k)))))

설탕배달(2839번)

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다.
설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.
상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다.
예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.
상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

n = int(input())
vinyl = 0

while True:

    if n%5 == 0:
        vinyl = n//5+vinyl
        print(vinyl)
        break

    elif n%5 != 0 and n%3 != 0 and n <3:
        print(-1)
        break

    else:
        n -= 3
        vinyl += 1

수찾기(1920번)

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다.
다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

def finding_numbers(base_items, find_num):
    start = 0
    mid = len(base_items) // 2
    end = len(base_items) -1

    while start <= end:
        if base_items[mid] == find_num:
            return 1
        elif base_items[mid] > find_num:
            end = mid - 1
        else:
            start = mid + 1
        mid = start + (end - start) //2

    return 0

base_count = int(input())
base_items = list(map(int, input().split()))
find_count = int(input())
find_items = list(map(int, input().split()))

base_items = sorted(base_items)

for i in range(find_count):
    print(finding_numbers(base_items, find_items[i])

프린터 큐(1966번)

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다.
여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다.
하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.
여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다.

t = int(input())
result = []
for i in range(t):
    n, m = map(int, input().split())
    Q = [(idx,val) for idx, val in enumerate(list(map(int, input().split())))]

    cnt = 0
    while True:
        cur = Q.pop(0)
        if any(cur[1]<x[1] for x in Q):
            Q.append(cur)
        else:
            cnt += 1
            if cur[0] == m:
                result.append(cnt)
                break
for i in result:
    print(i)