0. 서문

이상하게 금요일만 되면 라면을 먹게된다. 금요일의 학식이 맛이 없어서인가...그렇다고 하기에는 다른 조원들 이야기 들어보면 오늘 학식은 괜찮다던데. 비교적 이곳이 라면을 잘 끓여줘서 그런걸지도 모르겠다.

1. 멀티탭 스케줄링

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

최초에는 그냥 멀티탭 들어오는것만 체크해주면 문제 없는것 아닌가 싶어서 그냥 생각나는대로 바로 코드를 짰는데 제출하고 1초만에 바로 틀렸다고 나왔다.
어떻게, 테스트케이스는 정답이던데 1초만에 틀렸다고 나와버리는지...

import sys
input = sys.stdin.readline


n, k = map(int, input().split())
arr = list(map(int, input().split()))
plug = []
cnt = 0

for i in range(n):
    plug.append(arr[i])

for i in arr[n:]:
    if i in plug:
        continue
    else:
        plug.append(i)
        cnt += 1

print(cnt)

좀 더 생각해보니 일단 코드에 무작정 넣는게 아니고 일단 갯수가 정해져 있으니 갯수를 정해서 넣어 줄 필요가 있었다. 또한, 그렇게 해서 꽂을 수 있는 코드를 다 꽂은 상태에서 추가로 기존에 꽂혀있지 않은 전자기기를 쓸려고 한다면 앞으로 쓸 전자기기들을 파악해서 앞으로 쓰지 않을 전자기기 가 꽂혀 있다면 해당하는 전자기기를 플러그에서 먼저 빼고 가능한 나중에 쓰는 전자기기부터 빼는 그런 방식으로 코드를 짜야한다는것 까지는 생각 해 볼 수 있었다.

다만, 이 코드를 어떻게 짜야할지가 막막한 일이었기에 결국에는 답을 찾아보고 말았다.
사실상, 내가 작성했다고 볼 수 없는 코드이기에 다음에 따로 코드를 올리려 한다.

2. 동전

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

DP 문제들은 풀다보면 자괴감에 빠진다. 접근을 못할때가 많다. 이 문제도 똑같다. 접근이 쉽사리 되지 않는다. 재귀를 풀때랑 비슷한 느낌.
이놈의 규칙성을 알아야 하는데 예전부터 반복되는 규칙을 찾는다거나 하는 종류의 문제는 잘 못풀었던지라 이번 기회에 이쪽 능력이 좀 늘면 좋겠다. 제발.

동전 문제에 경우 종이에 1원부터 5원까지 나란히 두고 그걸로 10원까지 만드는 경우의 수를 다 쓰고 나서야 좀 알것같았다. 그래도 사실 정확한 식을 세우기 힘들어서 이것도 결국 답을 보고야 말았다. 언제쯤 되야 답을 안보고 풀 수 있을까...

import sys
T = int(sys.stdin.readline())

for _ in range(T):
    N = int(sys.stdin.readline())
    coins = list(map(int, sys.stdin.readline().split()))
    M = int(sys.stdin.readline())

    dp = [0] * (M+1)
    dp[0] = 1
    for coin in coins:
        for i in range(1, M+1):
            if i >= coin:
                dp[i] += dp[i-coin]
    print(dp[M])

3.LCS

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

문제의 예시에서 왜 저 답이 나오는지 이해가 안가서 고생한 문제였다. 수학적 지식이 부족해서 생긴 문제였던거같다. 아님 추가로 이해력도 부족했거나. 때때로, 프로그래머가 수학을 잘 못해도 괜찮다는걸 본거같은데 거짓말이다. 잘해야한다는 생각밖에 들지 않는다.

이 문제의 경우 다이내믹 프로그래밍 완전 정복 이라는 책에 설명이 적혀 있어서 해당하는 부분을 보고 참고하여 풀 수 있었다.

import sys

A = sys.stdin.readline().strip().upper()
B = sys.stdin.readline().strip().upper()

lcs = [[0] * (len(A)+1) for _ in range(len(B)+1)]

for i in range(1, len(B)+1):
   for j in range(1, len(A)+1):
       if B[i-1] == A[j-1]:
           lcs[i][j] = lcs[i-1][j-1] + 1
       else:
           lcs[i][j] = max(lcs[i][j-1], lcs[i-1][j])

print(lcs[-1][-1])