100년 뒤 개발자 한승규입니다.

https://www.acmicpc.net/problem/1339

일의 자리는 * 1
십의 자리는 * 10

백의 자리는 * 100

으로 배열에 각 알파벳 마다 수를 계산해서 가지고 있는다.

그리고 큰 순으로 정렬을 해서 9, 8, 7, .... 이렇게 곱하기 해준 후 더해주면 된다.

import sys

word = [0 for i in range(ord('Z') - ord('A') + 1)]

for i in range(int(sys.stdin.readline().strip())):

    input_word = str(sys.stdin.readline().strip())

    cur_index = 1

    while input_word:
        word[ord(input_word[-1]) - ord('A')] += cur_index
        cur_index *= 10
        input_word = input_word[:-1]

word.sort(reverse=True)

result = 0

for i in range(10):
    result += (word[i] * (9-i))

print(result)

https://www.acmicpc.net/problem/1715

그리디답게 생각하는 데 오래 걸리지 않는다.

해당 카드 뭉치들에서 가장 작은 거 2개를 뽑아오는 것이 가장 최적일 것이다.

그러면 가장 작은 뭉치를 어떻게 가져오느냐를 생각해야 하는 데, 당연히 정렬이 먼저 떠오를 것이다.

여기서 퀵 정렬을 사용하면 nlogn의 시간복잡도가 나올 것인데, 지속적으로 가장 작은 것을 가져오려면 우선순위 큐를 사용하는 것이 logn으로 시간복잡도가 더 낮을 것이다.

그렇기 때문에 우선순위 큐를 사용하도록 한다.

import sys
import heapq

heap = []

for _ in range(int(sys.stdin.readline().strip())):
    heapq.heappush(heap, int(sys.stdin.readline().strip()))

result = 0

while len(heap) > 1:
    A = heapq.heappop(heap)
    B = heapq.heappop(heap)

    result += (A + B)
    heapq.heappush(heap, A + B)

print(result)

heap이라는 우선순위큐를 만들고 그곳에다가 카드의 수를 입력 받는다.

그리고는 while 반복문으로 카드 뭉치가 하나 남을 때까지 카드들을 뭉쳐주고 그렇게 뭉친 카드 뭉치는 다시 우선순위큐로 넣을 수 있도록 한다.

https://www.acmicpc.net/problem/1946

문제를 이해하는 시간만 한시간 정도 걸렸던 것 같다.

당연히 점수인 줄 알았는 데, 너무 이해가 되지 않아 질문게시판 찾아보니까 순위라고 하더라....

무조건 한 명 이상은 뽑을 것이니 처음 result를 1로 해준다.

그러고는 그냥 단순히 앞 순위로 정렬해주고, 반복문으로 순위를 점점 올려가며 가능한 친구들만 받고 result를 +1해준다.

import sys

for i in range(int(sys.stdin.readline().strip())):
    candidate = sorted([list(map(int, sys.stdin.readline().split())) for _ in range(int(sys.stdin.readline().strip()))])
    top = 0
    result = 1

    for t in range(1, len(candidate)):
        if candidate[t][1] < candidate[top][1]:
            top = t
            result += 1

    print(result)

https://www.acmicpc.net/problem/16953

아무리 생각해도 이 문제는 그리디보다는 BFS에 가깝다고 생각을 한다.

중복이 있으면 반복이 오래걸리고 같은 계산을 반복하기에 set으로 만들어서 중복을 제거하도록 했다.

우선 첫 수를 집합에 넣는다.

그리고 반복문을 실행하는 데, 조건은 B가 집합에 없고 집합이 비어있지 않는다는 조건이다.

반복문이 실행할 때마다, 임시로 저장할 집합을 만들고 해당 집합에 전역 집합에 있는 수에 *2, *10 + 1 한 값을 다 넣어두고 해당 집합을 전역 집합으로 바꿔준다.그리고 반복문이 실행될 때마다 결과값을 +1 해준다.

출력에서는 B가 발견이 되어 집합에 수가 남아있다면 result를 출력하고, 아니라면 B를 찾지 못하기 때문에 -1을 출력해준다.

import sys

A, B = map(int, sys.stdin.readline().split())

greedy = set()
greedy.add(A)

result = 1

while B not in greedy and greedy:

    current_greedy = set()

    while greedy:
        element = greedy.pop()
        if element * 2 <= 10 ** 9:
            current_greedy.add(element * 2)
        if element * 10 + 1 <= 10 ** 9:
            current_greedy.add(element * 10 + 1)

    result += 1
    greedy = current_greedy


print(result if greedy else -1)

https://www.acmicpc.net/problem/1931

학교에서도 배웠던 문제이고, 그리디라는 것을 알고 푸니 어렵지 않았다.

어떻게 정렬할지만 최대한 생각을 해보았다.

당연히 끝나는 시간을 기준으로 빨리 끝나는 거 부터 쭉 줄 세우고 가능한 회의만 받도록 했다.

빨리 끝나기만 하면 얼마나 걸리든지, 다음 회의를 받을 수 있기 때문이다.

중간에 정렬할 때 생각 못한 부분들이 있어서 오래 걸리긴 했다.

import sys

meeting = sorted([list(map(int, sys.stdin.readline().split())) for i in range(int(sys.stdin.readline().strip()))],
                 key=lambda x: (x[1], x[0]))

time = 0
result = 0

while meeting:
    start_time, end_time = meeting.pop(0)
    if start_time >= time and end_time < 2 ** 31:
        time = end_time
        result += 1

print(result)

https://www.acmicpc.net/problem/1213

이번 문제는 카테고리가 그리디이긴 하지만, 딱히 그리디를 생각하지는 않았다.

그냥 단순히 정렬 후 같은 것들은 묶어주고, 만약 문자가 짝수개이면 하나의 문자도 혼자있으면 안되며 홀수인 경우에는 하나의 문자만 홀로 있어야 한다.

다른 거 수와 문자열의 길이만 비교해서 구현하면 쉬운 문제로 딱히 로직에 관련해서는 설명하지 않도록 하겠다.

import sys

input_str = sorted(list(sys.stdin.readline().strip()))

start = ""
mid = ""
end = ""

chance = 0 if len(input_str) % 2 == 0 else 1

cur_char = ""

for i in input_str:
    if cur_char == "":
        cur_char = i
    else:
        if cur_char == i:
            start = start + cur_char
            end = cur_char + end
            cur_char = ""
        else:
            chance -= 1
            mid = cur_char
            cur_char = i

if cur_char != "":
    mid = cur_char

if chance >= 0:
    print(start + mid + end)
else:
    print("I'm Sorry Hansoo")

https://www.acmicpc.net/problem/11399

이번 주는 그리디 알고리즘이다.

그리디가 동적프로그래밍보다 쉽다고 생각한다.

그리디는 그냥 계속 최소 혹은 최대만 가져오면 된다고 생각하기 때문..

해당 문제도 그냥 정렬 후 가장 작은 값부터 차례대로 가져올 수 있도록 했다.

import sys

N = int(sys.stdin.readline().strip())

P = sorted(list(map(int, sys.stdin.readline().split())))

cur_time = 0
result = 0

for i in P:
    cur_time += i
    result += cur_time

print(result)

https://www.acmicpc.net/problem/2293

별로 어렵다고 생각하지 않았지만, 풀다보니 굉장히 어려운 문제였다.

단순하게 배열로 쭉 만들어서 더하며 나가면 된다고 생각했는 데, 구성이 같은 것들을 제외하느라 시간을 오래쓰게 되었다.

이해가 잘 될 수 있도록 보기를 통해 분석해보도록 하자.

보기는 1, 2, 5이 3가지 동전으로 10을 채우는 경우를 구하는 것이다.

경우의 수를 모두 구해보자.

이렇게 10가지의 경우가 나오게된다.

이렇게보면 나누기로도 구할 수 있을 거 같은데, 일단 당연히 DP로 풀어야 하기에 생각해보지 않았다.

경우의 수가 중복이 되면 안되기 때문에 각 코인은 한 번씩 코인의 개수만큼 반복해야 한다.

일단 코인을 입력받으면, 해당 코인의 가치만큼의 경우의 수가 +1 되는 것이다.

그리고 1부터 목표가치만큼 진행하며, 만약 m의 가치의 경우의 수가 3이라면 m+(코인의 가치)의 가치에 해당하는 경우의 수도 3 늘어나게 되는 것이다.

이렇게 반복문을 진행해가면 된다.

import sys

n, k = map(int, sys.stdin.readline().split())

value = [0 for i in range(k+1)]

for i in range(n):
    coin = int(sys.stdin.readline().strip())
    if coin <= k:
        value[coin] += 1
    for t in range(1, (k+1) - coin):
        value[t+coin] += value[t]

print(value[-1])