Ailysaku's PS blog

유형 : 다이나믹 프로그래밍 / 그리디

그리디 아이디어를 떠올리고 DP로 구현해야 하는 문제입니다.

문제에서 요구하는 최종 상태는

1, 2, 3, 4 . . ., N 입니다.

따라서,

서로 이웃한 두 수 x, x + 1 이 현재 배열에서도 같은 순서로 등장한다면,
이 두 수는 굳이 움직일 필요가 없습니다.

1 2 4 3

으로 줄이 서있다고 가정해봅시다.

1 2 3 이 가장 길게 연속으로 이어짐으로 건들 필요가 없습니다.

4 는 연속되지 않음으로 옮겨야 합니다.

4 를 뒤로 옮기면 1 2 3 4 로 1번의 바꾸기로 오름차순을 만들었습니다.

이번엔

1 2 5 4 3

으로 줄이 서있다고 가정해봅시다.

이 역시 1 2 3 이 가장 길게 연속으로 이어짐으로 건들 필요가 없습니다.

5 4 의 위치는 옮겨야 합니다.

5 와 4 를 뒤로 적절히 옮기면 1 2 3 4 5 로 2번의 바꾸기로 오름차순을 만들었습니다.

즉, 가장 잘 정렬된 어린이 배열을 유지하고 나머지 줄 잘못 선 분탕치는 어린이들을 처리하는게 최선의 움직임입니다.

따라서 문제의 답은,

P[i] = P[i - 1] + 1 (i  > 0) 을 성립하는 최장 길이 연속 수열을 찾고 N 에 뺀 값

입니다.

최장 길이 연속 수열을 찾아봅시다.

어떻게?

- DP 로!

점화식은

dp[x] = dp[x - 1] + 1

위와 같습니다.

현재 수 X 는 X - 1 의 최장 길이에 1 을 더한 값이다.

import sys

input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

dp = [0] * (N + 1)

for x in arr:
    dp[x] = dp[x - 1] + 1

print(N - max(dp))

유형 : 그리디

이왜실..? 골드 5로 올라가도 이상하지 않을 문제라고 생각합니다.

1. 3×3 영역의 왼쪽 상단을 (i, j)로 정의한다.

2. (i, j)에 있는 애들은 독립적으로 바꿀 수 있다.

3. (i, j)들을 모두 바꿔야만 똑같이 만들 수 있으니 필수로 바꿔야 한다.

4. 뒤집기의 순서는 결과에 영향을 주지 않는다. (교환 법칙이 성립)

5. (i, j)를 모두 바꿨을때의 결과는 하나 뿐이다.

6. 결과가 목표 배열과 다르면 목표에 도달할 수 없다.

import sys

input = sys.stdin.readline

size_y, size_x = map(int, input().split())
board_origin = [list(input().rstrip()) for _ in range(size_y)]
board_goal = [list(input().rstrip()) for _ in range(size_y)]

def flip_arr(x, y):
    for yi in range(y, y + 3):
        for xi in range(x, x + 3):
            board_origin[yi][xi] = '1' if board_origin[yi][xi] == '0' else '0'

cnt = 0
for y in range(size_y - 2):
    for x in range(size_x - 2):
        if board_origin[y][x] != board_goal[y][x]:
            flip_arr(x, y)
            cnt += 1

print(cnt if board_origin == board_goal else -1)

유형 : 수학 / 다이나믹 프로그래밍 / 브루트포스

다양한 풀이가 존재하는 문제입니다.

삼각형은 가장 긴 변의 길이가 다른 두 변의 길이의 합보다 작아야함으로,

각 길이를 부르트포스 하면 됩니다.

부르트포스 풀이는 O(N^2)입니다.

import sys

input = sys.stdin.readline

N = int(input())

cnt = 0

for i in range(1, N + 1):
    for ii in range(i, N + 1):
        iii = N - (i + ii)

        if iii >= i + ii:
            continue

        else:
            if ii > iii:
                break

            cnt += 1

print(cnt)

하지만, N의 출력을 자세히 관찰하다보면...

N / 답

0 0
1 0
2 0
3 1
4 0
5 1
6 1
7 2
8 1
9 3
10 2
11 4
12 3
13 5
14 4
15 7
16 5
17 8
18 7
19 10
20 8
21 12
22 10
23 14
24 12
25 16
26 14
27 19
28 16
29 21
30 19
.

.

.

패턴이 보입니다.

N이 홀수, 짝수일때를 나눠보면 확실히 도드라집니다.

이를 DP로 만든다면 O(N)에 해결할 수 있습니다.

import sys

input = sys.stdin.readline

max_length = 50001
dp = [0] * max_length

a = 1
b = 1
c = 0
d = 0

for i in range(6, max_length, 2):
    c += 1
    
    if c == 1:
        dp[i] = dp[i - 2] + a
        a += 1
    
    else:
        if c == 2:
            dp[i] = dp[i - 2] + d
            d += 1
        
        if 2 < c <= 6:
            dp[i] = dp[i - 2] + b

    if c == 6:
        c = 0
        b += 1

a = 1
b = 1
c = 0
d = 0

for i in range(3, max_length, 2):
    c += 1
    
    if c == 1:
        dp[i] = dp[i - 2] + a
        a += 1
    
    else:
        if c == 2:
            dp[i] = dp[i - 2] + d
            d += 1
        
        if 2 < c <= 6:
            dp[i] = dp[i - 2] + b

    if c == 6:
        c = 0
        b += 1

N = int(input())
print(dp[N])

여기서 한발짝 더 나아가면 무려 O(1)에 해결할 수 있습니다.

패턴의 공식화를 통해서 말이죠.

import sys

input = sys.stdin.readline

N = int(input())

if N % 2 == 0:
    print(int(round(N ** 2 / 48)))

else:
    print(int(round((N + 3) ** 2 / 48)))

유형 : 그리디

DP 풀이를 떠올렸지만 몇개의 연료를 사야하는지 구하는 과정에서 O(N), 배열을 탐색하는데에 O(N), 최종적으로 O(N ^ 2)의 풀이가 되어 N(10만)이 들어오면 시간초과가 확정입니다.

따라서 그리디 유형일것으로 의심이 가능합니다.

문제를 관찰하다 보면 싼 곳에서 많이 사는 게 이득 이라는 생각을 첫번째로 하게됩니다.

그리고 싼 곳에서 더 싼 곳까지 필요한 기름을 사는 게 최선이라고 생각됩니다.

import sys

input = sys.stdin.readline

# 싼 곳에서 더 싼 곳까지 도달하는데 필요한 기름을 사는게 최선

N = int(input())
dist = list(map(int, input().split())) + [0]
city = list(map(int, input().split())) + [0]

minimum = 10 ** 20
cost = 0
pointer = 0

while pointer < N:
    minimum = min(minimum, city[pointer])
    fuel = 0

    for i in range(pointer + 1, N + 1):
        fuel += dist[i - 1]

        if city[i] < minimum:
            cost += city[pointer] * fuel
            pointer = i
            break

print(cost)

제 풀이는 이렇지만 그리디 아이디어를 좀 더 단순화하면 더 효율적이고 직관적인 코드를 작성할 수 있습니다.

지금까지 가장 싼 주유소 가격으로 다음 거리만큼 비용을 더한다.

import sys

input = sys.stdin.readline

N = int(input())
dist = list(map(int, input().split()))
city = list(map(int, input().split()))

minimum = city[0]
cost = 0

for i in range(N - 1):
    minimum = min(minimum, city[i])
    cost += minimum * dist[i]

print(cost)

생각해낸 풀이가 최선인지, 더 단순화할 수 있는지 고민하는 것도 필요한 과정인 것같습니다.

유형 : 수학 / 정수론 / 다이나믹 프로그래밍

DP의 냄새가 스멀스멀 나는 문제입니다.

경우의 수를 구하는게 목표니 완전탐색 코드를 짜서 답의 경향성을 파악해봅시다.

def search(depth):
    if depth == max_depth:
        s.add(''.join(arr))
        return

    for i in range(n):
        for ii in range(n):
            if i == ii or check[i] or check[ii]:
                continue

            arr[i], arr[ii] = arr[ii], arr[i]
            check[i], check[ii] = True, True
            search(depth + 1)
            arr[i], arr[ii] = arr[ii], arr[i]
            check[i], check[ii] = False, False

for n in range(2, 13):
    s = set()
    max_depth = n // 2
    arr = [str(i) for i in range(1, n + 1)]
    check = {i : False for i in range(n)}

    search(0)
    print(len(s))

출력 :

1
3
3
15
15
105
105
945
945
10395

10395

뭔가 패턴이 보이는 것 같습니다.

1. 수는 두번씩 반복되고 있다. (N이 1이면 답은 1이다)

2. 3 / 1 = 3, 15 / 3 = 5, 105 / 15 = 7 . . .  증가된 수와 이전 수를 나누면 2씩 증가하는 등차수열 몫을 가진다.

이 패턴을 기반으로 다음 수를 쉽게 예측할 수 있을겁니다.

10395의 다음 수는 10395 * (9 + 2) = 114345 가 되겠죠.

이제 패턴을 알고있기 때문에 어렵지 않게 DP배열을 만들어 답을 구할 수 있습니다.

정해는 (N - 1)!! 이지만 다이나믹 프로그래밍이 조금 더 직관적으로 다가오는 느낌입니다.(물론 제가 수학을 못해서 더더욱 그런 것같네요;;)

import sys

input = sys.stdin.readline

max_length = 100001
MOD = 10 ** 9 + 7
dp = [0] * max_length
dp[1] = 1
dp[2] = 1

x = 3
for i in range(3, max_length - 1, 2):
    dp[i] = (dp[i - 1] * x) % MOD
    dp[i + 1] = dp[i]
    x += 2

N = int(input())
print(dp[N])

유형 : 해시를 사용한 집합과 맵 / 구현

실랜디 하다가 만난 문제입니다.

N이 1000인걸 봐선 O(N ^ 2)이 정해라고 추정할 수 있습니다.

문제의 핵심은 아래와 같습니다.

늦게 들어간 차량이 앞서 들어간 차량보다 먼저 나온다면 그 차량은 추월한 차량이다.

예를 들어봅시다.

A B C D 순서로 들어가서

D C A B 순서대로 나왔다고 가정해봅시다.

먼저 답을 저장할 집합을 하나 만들어주고, 순서대로 탐색합니다.

A를 기준으로 D는 A보다 뒤에있다가 앞으로 간, 즉 추월한 형태입니다.

B 역시 추월한 형태입니다.

정답 집합엔 D, C가 들어갑니다.

B를 기준으로 D, C는 B보다 뒤에있다가 앞으로 간 형태입니다.

하지만 A는 원래부터 앞에 있었기 때문에 추월이 아닙니다.

정답 집합엔 D, C가 들어갑니다.

이를 반복하면,

정답 집합엔 D, C가 들어있게 됩니다.

이 차량들이 바로 추월한 차량입니다.

따라서 정답은 2가 됩니다.

즉, 들어갔을 때의 위치와 나왔을 때의 위치를 상대적으로 비교해주면 됩니다.

import sys

input = sys.stdin.readline

N = int(input())

car_in = {}
car_out = {}

for i in range(N):
    name = input().rstrip()
    car_in[name] = i

for i in range(N):
    name = input().rstrip()
    car_out[name] = (i, car_in[name])

passing = set()

for i in car_in:
    for ii in car_in:
        if car_out[i][0] > car_out[ii][0] and car_out[i][1] < car_out[ii][1]:
            passing.add(ii)

print(len(passing))