끄적끄적

유형 : dp

문제풀이

* 지금 설명할 풀이는 효율이 좋지 못합니다.

 b 도시에 i번째로 도착했을 때, 가능한 기내식 점수들의 합은 dp[a][i-1]+air[a][b] 가 됩니다. (air[a][b]는 a에서 b 구간 비행기의 기내식의 점수)

 따라서 dp[b][i]의 점화식은 아래와 같이 쓸 수 있습니다.

 dp[b][i] = max(dp[a][i-1]+air[a][b] for b보다 작은 모든 a)

 다만 위의 식을 진행하는 데에 있어서, i-1번째로 a에 도착한 경우와 a에서 b구간의 비행기가 있다는 조건을 위한 조건문이 추가로 들어가야합니다.

 위의 점화식을 b를 n까지, i는 m까지 반복 한 후, dp[n]의 최댓값을 반환하면 됩니다.

Python Code

line13에 try 문이 들어간 이유는 if문을 만족하는 a가 하나도 없는 경우 max함수에서 에러가 발생하기 때문입니다.

문제링크

유형 : dp

문제풀이

 포도주 시식 문제와 유사하지만, 마지막 계단을 반드시 밟아야한다는 제한이 있다. 

 따라서 i번째 계단의 점수가 s[i]라 하면, i번째 계단을 밟았을 때의 최대 점수 dp[i]는 다음과 같이 주어진다.

 dp[i] = max(dp[i-2]+s[i], dp[i-3]+s[i-1]+s[i])

 즉, 2칸 전 계단을 밟고 이번 계단을 밟거나, 3칸 전 계단을 밟고 전칸을 밟고 이번 계단을 밟거나 두가지 조건이 가능하다.

list 초기화와 append

 위의 문제를 해결하는데 있어서, dp를 먼저 빈 list로 선언한 후 append로 하나씩 채워갈 수도 있고, dp를 길이가 n인 리스트로 선언한 후, i번째 요소를 바꿔가는 방법이 있는데, 후자가 효율적이다. 전자로 통과한 후, 후자의 방법으로 바꾸었더니 80ms 에서 56ms로 줄었다.

Python Code

유형 : 스택

풀이과정

 Stack이란 후입선출하는 자료구조로 이를 이용하여 괄호의 균형을 체크한다.

 stack은 그냥 list를 선언하여 활용했는데, 어차피 맨 뒤의 것만 지울것이기 때문이다(list.pop()). 만약 앞의 것을 지워야한다면 deque를 선언하여 활용하는 것이 좋다.

 1. 문자열의 앞에서 부터 확인하는데, 왼괄호('(','[')를 만나면 stack에 넣어준다.

 2. 오른괄호를 만나면 stack의 맨 뒤의 원소를 확인하여 둘이 짝이면 stack의 맨 뒤의 것을 제거한 후 넘어가고(list.pop()), 짝이 맞지 않는다면 균형이 잡히지 않은 괄호이기 때문에 'no'를 리턴해준다.

입출력

 문제자체는 굉장히 쉬운 문제인데, 이상한데서 고생을 했다. 바로 입출력 문제인데, Python3에서 input()으로 입력을 받을 경우에는 뒤에 개행문자가 없지만 sys.stdin.readline()으로 입력을 받을 경우에는 뒤에 개행문자가 추가되어 입력이 들어온다. 따라서 이를 유의해야한다.

Python Code

주어진 N을 5와 3만을 사용하면서 가장 적은 수의 5와 3으로 나타내는 문제이다.

풀이과정

 $N = 5x + 3y$ 라 할때, $x$가 클수록 $x+y$가 작아질 것이다. 예를 들어, 30이라면 5를 6개 쓰는 것이, 3을 10개 쓰는것 보다 낫다.

1. 위에 썼듯, 5를 최대한 많이 사용하기 위해서 먼저, N이 5로 나누어 지는지 확인한 후,  나누어 진다면 answer에 N을 5로 나눈 몫을 더한 후 반환한다.

2. N이 5로 나누어지지 않는 경우에는, N에서 3을 빼준 후, answer 에 1을 더한다(3을 한번 사용).

3. N이 0이 될때까지 1~2 과정을 반복하되, N이 음수가 되는 경우에는 N이 5와 3만으로 표현되지 않는 것이므로 -1을 반환한다.

Python Code

유형 : dp

카드 n장을 살 때, 지불할 수 있는 최대 금액을 구하는 문제이다.

풀이과정

 카드 i 장을 구매하는데 필요한 금액을 dp[i] 이고, 카드 n장이 들어있는 팩의 가격이 p[n]라 하면, dp[i]는 아래와 같다.

 dp[i] = dp[i-n] + p[n]

 가능한 모든 n에 대하여 dp[i]가 최대값이 되도록 update해나가면 된다.

Python Code

유형 : bfs

풀이과정

1. ripen을 deque로 선언한 후, 토마토들의 정보를 읽으며 익은 토마토의 인덱스 (i,j)를 넣는다.

2. ripen에서 popleft로 하나씩 꺼내가며, 토마토의 이웃을 체크하고 익지 않은 토마토가 있으면 상태를 1로 바꾸어주고 ripen에 넣는다. 이때, time step을 세기위해, 각 time step마다, ripen에서 꺼내기 전에, ripen에 몇개의 요소가 들어있는지 체크해두고 popleft로 체크된 수 만큼만 빼고, 새로 넣는 토마토는 오른쪽으로 넣는다.

3. ripen이 빌때까지 2를 반복한 후, 장애물의 숫자와 익은 토마토의 숫자의 합이 m*m 일 경우에는 시간을, 아닐경우에는 -1을 반환한다.

Python Code

* 편의를 위해서 tomato는 (m+2)*(m+2) 행렬로, 가장자리를 -1(장애물)로 채웠습니다.

문제풀기

카카오 코드 페스티벌 2018 본선 문제

 입출금 로그를 보고 잘못된 부분이 있는지, 없다면 최소 충전금액은 얼마인지 알아내는 문제이다.

풀이과정

 먼저, a, b를 list로 가지고 있을 필요없이 입력받고 바로바로 처리하면 효율적으로 문제를 해결할 수 있다.

 minB는 0이 아닌 b의 최솟값이며, lastB는 이전 step의 b값이 된다.

 a+lastB가 음수인 경우에는 충전이 필요하며 충전 금액 temp는 아래와 같이 주어진다.

 temp = b - a - lastB

 충전금액은 최소충전금액의 배수만 가능하므로, 최소충전금액(변수 pay)은 충전액들의 최소 공배수가 되고, 이를 해결하기 위해 pay 변수를 계속해서 pay변수와 위의 temp 변수의 최대공약수로 갱신해준다.

 로그가 잘못 되었을 조건은 아래와 같다.

 1. 각 step에서 잔액 b는 전 step에서의 잔액과 현 step에서의 입출금 a의 합으로 주어져야하는데, b = lastB + a 를 만족하지 않으면 그 로그는 잘못된 로그이다.

 2. 최소충전금액이 pay이므로, 입출금 후의 잔액의 최솟값 minB는 pay보다 작아질 수 없다. 따라서 minB < pay 인 경우 그 로그는 잘못된 로그이다.

Python Code

문제풀기

유형 : 그리디

빨리 끝나는 회의부터 처리해야 한다. 이때, 끝나는 시간이 똑같은 회의의 경우, 시작 시간이 빠른 회의부터 처리한다.

코드

import sys

n=int(sys.stdin.readline())
times = []
for _ in range(n):
    times.append(tuple(map(int,sys.stdin.readline().split())))
  
times.sort()
times.sort(key=lambda x: x[1])
now,ans=0,0
for time in times:
    if time[0]>=now:
        ans+=1
        now=time[1]
print(ans)

정렬

 위의 코드에서는 times.sort()로 회의 시작 시간을 기준으로 정렬을 한 후, 회의 종료 시간을 기준으로 한번 더 정렬을 함으로써 위에서 언급한 규칙을 만족시켰다.

 하지만, 아래와 같이 comparator를 직접 정의함으로써 한번에 정렬할 수도 있는데, 내장함수로 두번 정렬하는 위의 방법이 훨씬 효율적이었다. ( 위의 방법 : 메모리 44944kb, 시간 328ms, 아래의 방법 : 메모리 50360kb, 시간 552ms)

from functools import cmp_to_key

def compare(x, y):
    if x[1] < y[1] :
        return -1 
    elif x[1] > y[1] :
        return 1
    else: 
        if x[0] < y[0] :
            return -1
        else:
            return 1
times.sort(key=cmp_to_key(compare))

문제풀기

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