[백준]230306-09 문제풀이

11053. 가장 긴 증가하는 부분 수열

import sys
input = sys.stdin.readline

N = int(input())
lst = list(map(int, input().split()))
dp = [1] * N
ans = 1
for i in range(1, N):
    for j in range(i):
        if lst[j] < lst[i] and dp[j] >= dp[i]:
            dp[i] = dp[j] + 1
            if dp[i] > ans:
                ans = dp[i]

print(ans)

LIS 문제의 기본. dp가 어려워서 쉬운것부터 도전해보려고 했는데 정말 발상부터가 쉽지 않다...이분탐색을 활용해 nlogn으로 푸는 방법도 있지만 일단 쉬운 문제는 n^2으로 해결이 되는 듯하다

2565. 전깃줄

import sys
input = sys.stdin.readline

N = int(input())
lst = [list(map(int, input().split())) for _ in range(N)]
lst.sort()
dp = [1] * N
maxi = 1
for i in range(N):
    for j in range(i):
        if lst[i][1] > lst[j][1] and dp[i] <= dp[j]:
            dp[i] = dp[j] + 1
            if dp[i] > maxi:
                maxi = dp[i]

ans = N - maxi
print(ans)

LIS의 응용 문제, 별반 다를 것은 없지만 이게 dp 문제라는 걸 알아채기가 정말 쉽지 않은 듯하다. 현재 컬럼의 숫자와 이어진 컬럼의 숫자 쌍에 대해 둘 다 크면 증가하는 것으로 보고 가장 긴 증가하는 부분수열을 찾고 전체 전깃줄 수에서 빼주면 되는 문제

1213. 팰린드롬 만들기

import sys
input = sys.stdin.readline

a = input().strip()
temp = []
ans = []
for i in a:
    if i not in temp:
        temp.append(i)
        continue
    for j in range(len(temp)):
        if temp[j] == i:
            ans.append(temp.pop(j))
            break
if len(temp) > 1:
    print("I'm Sorry Hansoo")
elif len(temp) == 1:
    ans.sort()
    sna = reversed(ans)
    print(*ans, sep='', end = '')
    print(temp[0], end = '')
    print(*sna, sep='')
else:
    ans.sort()
    sna = reversed(ans)
    print(*ans, sep='', end = '')
    print(*sna, sep='')

팰린드롬수 만드는 간단한 문자열 문제. 쉽지만 문자열 까먹으면 안되니까 가끔씩 풀어주기

13164. 행복 유치원

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
students = list(map(int, input().split()))
diff = []

for i in range(1, n):
    diff.append(students[i]-students[i - 1])
diff.sort(reverse=True)
ans = sum(diff[k-1:])
print(ans)

그리디 치고는 풀만해서 괜찮다고 생각했으나, 이해가 안되는 부분이 있었다. 차잇값을 저장한 리스트를 sort할 때 reverse를 하지 않고 diff[:- (k - 1)]을 한 것과 reverse=True이고 diff[k-1:]을 한 것이 다르게 나타난 것. 이유가 뭔지는 차차 생각해보자...