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

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])

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

일단 문제가 DP이기 때문에 보자마자 단계가 있는지 확인한다.

일단 바로 각 층으로 단계를 구별할 수 있을 것 같다.

그렇게 단계를 나누면, 각 단계별로 영향을 받는 것은 해당 단계의 전 단계이다.

전 단계를 보고 해당 단계의 최대값을 구하며 내려가면 될 것 같다.

import sys

n = int(sys.stdin.readline())

max_list = [0 for i in range(n)]

for i in range(n):
    level = list(map(int, sys.stdin.readline().split()))
    cur_max_list = list()

    for t in range(i+1):
        if t == 0:
            cur_max_list.append(max_list[0] + level[0])
        elif t == i:
            cur_max_list.append(max_list[-1] + level[i])
        else:
            cur_max_list.append(max(max_list[t-1], max_list[t]) + level[t])
    max_list = cur_max_list

print(max(max_list))

각 층의 첫 번째 칸과 마지막 칸은 경우가 그냥 하나 밖에 존재하지 않는다.

그냥 위의 칸 + 현재 칸이다.

해당 값은 그냥 바로 구해서 넣어줄 수 있도록 하고, 그 사이의 칸들은 윗 단계에서 내려올 수 있는 2가지 수 중에서 큰 값을 가져와 본인의 수와 더해 최대값을 구할 수 있도록 하였다.

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

이번주도 DP가 주제이다.

DP = 단계별로 값을 저장이기 때문에 문제를 보자마자

한 줄마다 각 단계를 어떻게 저장할 수 있을지를 먼저 생각해보았다.

일단 각 줄마다 영향을 받는 것은 해당 줄의 전 줄이다.

만약 3번째 줄을 본다면, 2번째 줄의 집에만 영향을 받고 1번째 줄의 집에 색에는 영향을 받지 않는다.

그럼 한 줄씩 진행해가며, 전 단계의 집을 살핀 후 각 색마다 만들 수 있는 최소 비용을 구한다.

그렇게 한 단계씩 DP를 진행해가며, 마지막에는 그 중에서 최소값을 구해 출력하게 된다.

import sys

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

min_list = [0 for i in range(3)]

for i in range(N):
    color = list(map(int, sys.stdin.readline().split()))
    min_list = [
        min(min_list[1], min_list[2]) + color[0],
        min(min_list[0], min_list[2]) + color[1],
        min(min_list[0], min_list[1]) + color[2]
    ]

print(min(min_list))

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

옛날에 굉장히 고생했었던 LCS이다.

그 기억 때문에 이번 동적 프로그래밍에서 이번 문제를 뽑은 거 같기도 하다.

당연히 동적 프로그래밍답게 배열이 등장한다.

하지만 여기서는 기존과는 다르게 2차원 배열이다.

이 생각을 못해서 옛날에 굉장히 고생했었다.

일단 이런 식의 배열을 생성한다.

구하는 방식은 ACAYKP로 문자열을 기준 잡고

C, CA, CAP, CAPC, CAPCA, CAPACK를 순서대로 비교해가며 가장 긴 공통 수열을 찾아가는 방식이다.

각 문자열의 가장 앞에는 빈 문자열을 둔 것이고, 당연히 빈 문자열이기 때문에 공통 수열의 길이는 0이다.

우선 C부터 비교를 해보자

가장 긴 공통 수열은 C 하나 일 것이다.

그러면 ACAYKP에서 C 이후로는 가장 긴 공통 수열의 길이가 1이 될 것이다.

그 후로는 A를 비교해본다.

현재 비교하는 문자열은 CA이다.

ACA 이후로는 CA가 겹치기 때문에 가장 긴 공통 수열의 길이는 2가 된다.

마지막으로 CAP까지만 비교해보자.

CAP가 겹치기 때문에 길이는 3이 나오게 된다.

여기서 배열은

만약 해당 문자가 같을 경우(first_word[i] == second_word[t])에는 dp[i][t] = dp[i-1][t-1] + 1을 저장해주고

만약 해당 문자가 다른 경우(first_word[i] != second_word[t])에는 do[i][t] = max(dp[i][t-1], dp[i-1][t])로 저장해주면 된다.

그렇게 만들어진 최종 배열이다.

만들어진 코드는 다음과 같다.

import sys

first_word = list(sys.stdin.readline().strip())
second_word = list(sys.stdin.readline().strip())

max_length = max(len(first_word), len(second_word))

dp = [[0 for i in range(max_length + 1)] for t in range(max_length + 1)]

for i in range(len(first_word)):
    for t in range(len(second_word)):
        if first_word[i] == second_word[t]:
            dp[i][t] = dp[i-1][t-1] + 1
        else:
            dp[i][t] = max(dp[i][t-1], dp[i-1][t])


print(dp[len(first_word) - 1][len(second_word) - 1])