코딩테스트 대비 백준 문제 뽀개기 : dp

0. 출처

https://covenant.tistory.com/224?category=727170 

코딩테스트 대비를 위한 백준 문제 추천

0-2. 런타임 에러 발생 시 확인

https://blockdmask.tistory.com/550

[python] 파이썬 에러 종류 10가지

1. 평범한 배낭

- https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

- 해결 방법: https://gsmesie692.tistory.com/113 참고 

# dp[i][j] : 처음부터 i번까지의 물건을 살펴보고, 배낭 용량이 j일때 배낭에 들어갈 물건의 최대 가치 
# dp[i][j] = if w[i] > j  dp[i-1][j]  #i번째 물건의 무게 >  j이면 i번째 물건 안넣음. i-1번 까지의 최대값 넣음 
              else max( dp[i-1][j], dp[i-1][j-w[i]] + w[i] ) #i번째 물건을 넣지 않았을 때, i번째 물건 넣었을 때 최대값 넣음

 

- 유의 사항

# dp배열의 인덱스범위가 "값"이면 1~N으로 해야 함!!!!!!! ("~번째"까지면 0~N 가능.. )
# 1~N으로 맞추려면 배열 맨 앞에 값 넣기!! append(X) insert(0, value)로 하기!!! 

 

- 코드

 

import sys
input = sys.stdin.readline

def solution(N,K,things):
	things.insert(0,(0,0))

	dp = [ [0] * (K+1) for _ in range(N+1) ] #dp[i][j] : i번째 물건까지 살펴봤을 때, 용량이 j인 배낭에 들어갈 최대 가치 
	for i in range(1,N+1):
		for j in range(1,K+1):
			if things[i][0] > j:
				dp[i][j] = dp[i-1][j]
			else:
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-things[i][0]] + things[i][1] )
	return dp[N][K]

if __name__== "__main__":
	N,K = map(int,input().split())
	things = [ tuple(map(int,input().split())) for _ in range(N) ]
	answer = solution(N,K,things)
	print(answer)

 

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

2. 1학년

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

5557번: 1학년

- 문제: N개 숫자가 주어질 때, 1~N-1번째 숫자 사이에 + / - 을 넣어서 마지막 숫자와 값이 같아지는 등식을 만들려 할 때, 가능한 경우의 수는?

 

- 해결 방법: dp[i][j] ( i번째 전까지의 계산값이 j일 때, j와 남은 수들의 연산으로 결과값을 만들 수 있는 경우의 수)

- dp로 경우의 수 구하는 법!!!! : 작은 값부터 탐색 시작 ~ idx == N이면서 조건 만족시 1, else 0 return하고 idx < N일 땐 dp[idx] += go(idx+1) 방식으로 풀기

 

- 주의 사항: 이 문제처럼 하나의 idx에 대해 2번 이상 함수를 호출하게 될 경우, 맨처음 함수 인자 주의할 것 !!!! 0 / 1 중 무엇부터 시작해야하는지 판단하기! ... 이 문제에선 (0,0)이 아니라 (1,arr[0])으로 해야 한다. 0번째 값이 0인 경우에 2번 세지므로... 

#dp[i][j] : i번째 전까지의 계산값이 j일 때, j와 남은 수들의 연산으로 결과값을 만들 수 있는 경우의 수
#함수 호출 할 때, (0,0)이 아니라 (1,arr[0])으로 해야 함 -- 1번째 값이 0인 경우에 2번 세짐
#1차원 리스트 만들 때 [0] * N으로 하기 (N) 안됨
import sys
input = sys.stdin.readline

dp = []

def go(cnt,total,arr):
	global dp
	if dp[cnt][total] != 0:
		return dp[cnt][total]
	 	
	if cnt == N-1:
		if total == arr[N-1]:
			return 1
		else:
			return 0
	
	if total + arr[cnt] <= 20:
		dp[cnt][total] += go( cnt+1,total + arr[cnt],arr)

	if total - arr[cnt] >= 0:
		dp[cnt][total] += go( cnt+1,total - arr[cnt],arr)
	
	return dp[cnt][total]


if __name__ == "__main__":
	N = int(input())
	arr = list(map(int,input().split()))
	dp = [ [0]*(21) for _ in range(N) ]

	answer = go(1,arr[0],arr)
	print(answer)

 

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

3. 데스노트

- https://www.acmicpc.net/problem/2281

2281번: 데스노트

- 문제: 노트에 정해진 순서대로 N명의 이름을 적으려 한다. 이름 사이엔 빈 공간 한 칸을 두고 써야 하며, 각 줄에 이름을 이어서 쓰거나 새로운 줄에 쓸 수 있다. 다만 이름이 끝에서 쓰다 잘리면 그 줄에 이어서 못쓰고 반드시 다음 줄에 써야 한다. 각 줄의 끝에 사용하지 않고 남게되는 칸 수 제곱의 합이 최소가 되려 한다.(단 맨 마지막 줄 제외) 제곱합의 최소값은?

 

- 해결 방법: 

# 경우의 수를 구하는 dp : idx == N이고 조건 만족시 1 , else 0 return // dp[idx] += go(idx+1) + value .. 등

# 최소값을 구하는 dp: idx == N이면 return 0, dp[idx] = min ( ~~ go(idx+1) ) --> 이 방식대로 풀기

# dp[i][j] : i번째 이름을 쓰려하고, 현재 줄에서 남은 빈칸 수가 K일 때 지금까지 빈칸 제곱의 합

# i번째 글씨 쓰고, 다음 빈칸 개수 셀 때 -1 하면 안됨(빈칸 1칸 고려한 값). 만약 i번째 글씨 길이 == 노트 가로 길이 일 수 있으므로 인덱스 에러 고려해야 함

 

- 주의 사항: 

# 맨 처음 dp함수 시작을 (0,M)으로 하면 안됨!! 1) 새로운 줄에 쓸 때 rem*rem값이 쓸데없이 들어감 2) 이어붙일 경우 한 칸 띄어쓰게 됨  ==> (1,M-arr[0])으로 시작하기 --> 이것도 경우의 수가 2개 이상인 재귀 함수이므로 시작 값 잘 생각해야 함!! 

# 재귀가 1000번 정도 될 경우 sys.setrecursionlimit(10**6)

# dp[i][k] : i번째 글자를 넣으려 할 때, 현재 줄에서 남은 빈칸 수가 k일때 지금까지 빈칸 제곱의 합..! 
# 재귀가 1000번 넘어갈것 같으면 setrecurtionlimit()제한두기
# 다음줄에 작성할 때 -1을 더 해버리면 안됨(글씨 크기 == M일 수도 있으므로 인덱스 에러 고려해야 함)
# 맨 처음 dp 실행 할 때 (0,M)하면 안됨. 다음 줄에 하는거 계산할 때 rem*rem이 쓸데없이 들어감 + 이어 붙일 때 -1하는건 전에꺼랑 
# 차이두려고 하는건데 이렇게 되면 맨 처음에도 한 칸 띄어서 작성하게 됨 
import sys
input = sys.stdin.readline
MAX = sys.maxsize
sys.setrecursionlimit(10**6)
    
dp = [] 
def go(num,rem):
	global dp
	if num >= N:
		return 0
	
	elif dp[num][rem] != MAX:
		return dp[num][rem]
	
	else:
	 	#다음 줄에 작성하기
		next_rem = M - arr[num]
		dp[num][rem] = rem * rem + go((num + 1), next_rem)
		
		#현재 줄에 작성할 수 있는 경우, 최솟값 찾기
		if arr[num] < rem and rem > 0:
			next_rem = rem - arr[num] - 1
			dp[num][rem] = min(dp[num][rem], go((num + 1), next_rem))
	return dp[num][rem]

if __name__ == "__main__":
	N, M = map(int,input().split())
	arr = list( int(input()) for _ in range(N) )
	dp = list( [MAX] * (M+1) for _ in range(N) )
	
	answer = go(1, M - arr[0])
	print(answer)

 

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

4. 소형기관차

- https://www.acmicpc.net/problem/2616

2616번: 소형기관차

- 문제 : 1~N번 객차에 손님 수가 주어진다. 소형 기관차는 3대가 있고, 각 기관차가 최대로 데려갈 수 있는 객차 수가 주어진다. 3대의 소형 기관차를 이용하여 최대로 운송할 수 있는 손님 수는?

 

- 해결 방법: 

#dp[i][j]: i번째 객차까지 탐색하고, j개의 소형 기관차를 사용하였을 때 운송할 수 있는 최대 손님 수

# dp의 각 배열 index 의미가 "~개 사용", "합이 ~인 경우", 등의 특정 값과 관련된 경우는 0~K-1말고 0~K까지 해야 맘 편함ㅎ

# j값을 (0,1,2)로 하려 했다. ( 0 :1개 기관차 사용한 경우, 1: 2개기관차 사용한 경우), 근데 그렇게 되면 무조건 첫번째 객차를 사용해야 했다... 따라서 아예 선택 안했다는 의미를 살리고자 0,1,2,3으로 바꿨음!!

#dp[i][j]는 i번째 값을 선택 안했을 경우(dp[i-1][j])와 i번째 값을 사용했을 때 (dp[i-K][j-1] + sum(arr[i-K+1:i+1]))) 중 최댓값. 이 때 i는 연속된 객차 중 마지막 index 

 

#2616 소형기관차
# 1~N번 객차에 손님 수가 주어진다. 소형 기관차는 3대가 있고, 각 기관차가 최대로 데려갈 수 있는 객차 수가 주어진다. 3대의 소형 기관차를 이용하여 최대로 운송할 수 있는 손님 수는?
#dp[i][j]: i번째 객차까지 탐색하고, j개의 소형 기관차를 사용하였을 때 운송할 수 있는 최대 손님 수 
import sys
input = sys.stdin.readline

def solution(N,K,arr):
	dp = [ [0]*4 for _ in range(N)] 
	dp[K-1][1] = sum(arr[0:K]) #0~K번째 객차를 처음 선택했을 경우

	for i in range(K,N):
        #직전 최댓값을 선택하거나, i-K+1 ~~ i번째 객차를 선택했을 경우 
		dp[i][1] = max(dp[i-1][1], sum(arr[i-K+1:i+1]))
		dp[i][2] = max(dp[i-1][2], dp[i-K][1] + sum(arr[i-K+1:i+1]))
		dp[i][3] = max(dp[i-1][3], dp[i-K][2] + sum(arr[i-K+1:i+1]))
	
	return dp[N-1][3]

if __name__ == "__main__":
	N = int(input())
	arr = list(map(int,input().split()))
	K = int(input())
	
	answer = solution(N,K,arr)
	print(answer)

 

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

5. 괄호 

- https://www.acmicpc.net/problem/10422

10422번: 괄호

- 문제: 길이가 L인 올바른 괄호의 개수를 출력하라

- 해결 방법 : 카탈란 수 ( 한 가지 경우를 시행하면, 그와 쌍이되는 다른 경우를 반드시 시행해야 하는 모든 개수)

// Catalan(n) = 2nCn - 2nC(n+1) 

import math

def catal(n):
	return math.factorial(2*n) // math.factorial(n) * math.factorial(n+1)

# 10422 괄호
# 길이가 L인 올바른 괄호의 개수를 1,000,000,007로 나눈 나머지로 출력하기
import sys
import math
input = sys.stdin.readline

def catal(n):
    return math.factorial(2*n) // ( math.factorial(n) * math.factorial(n+1) )
    
if __name__ == "__main__":
    #길이가 i인 올바른 괄호 개수를 저장하는 배열 생성
    arr = [0]*5001
    arr[0] = 1
    for i in range(2,5001,2):
        arr[i] = catal(i/2) % 1000000007
    answer = []
    
    T = int(input())
    for _ in range(T):
        N = int(input())
        answer.append(arr[N])
        
    for x in answer:
        print(x)

 

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

6. 뮤탈리스크

- https://www.acmicpc.net/problem/12869

12869번: 뮤탈리스크

- 문제: N개의 SCV가 있고, 각 SCV는 체력이 있다.뮤탈리스크는 한번에 서로 다른 3개의 SCV를 공격할 수 있으며 순서대로 (9,3,1)만큼 공격할 수 있다. 모든 SCV를 파괴하기 위해 공격해야 하는 공격횟수의 최솟값을 리턴해라

 

- DP 해결방법:

# 처음엔 브루트 포스로 생각해서, 3개 SCV가 다 0이 될 때까지 answer = min(answer, solution(t[0],t[1],t[2]) + 1)로 탐색. -> 그 후에 뭘 메모이제이션 할까..하고 보니 함수의 인자로 건넸던 각 scv값들을 dp로 넣으면 되겠구나~! 

( N <= 3이고, 각 SCV 체력이 60이하이므로, 그래서 N개의 SCV체력을 각각 메모모이제이션할 수 있음)

# dp[i][j][k] : scv체력이 각각 i,j,k일 때 앞으로 필요한 최소공격횟수 

# dp[i][j][k] = min (dp[i][j][k], go(i-9,j-3,k-1) + 1)

 

- 유의사항:

#valueerror : 부적절한 값을 인자로 받았을 때, 매개변수에 들어갈 값이 없을 때 에러나는 경우가 많음!

import sys
from itertools import permutations
input = sys.stdin.readline
MAX = 61
INF = sys.maxsize

comb = list(permutations([1,3,9],3))
dp = list( list( [INF]*MAX for _ in range(MAX)) for _ in range(MAX) )# dp[i][j][k] : 각 체력이 i,j,k일때 앞으로 필요한 최소 공격 횟수... 그러면 dp[0][0][0] 값이 내가 원한 값 
		
def solution(a,b,c):
	a = max(a,0)
	b = max(b,0)
	c = max(c,0)
	if a == 0 and b == 0 and c == 0:
		return 0
	
	elif dp[a][b][c] != INF:
		return dp[a][b][c]

	else:
		global comb
		for co in comb:
			dp[a][b][c] = min(dp[a][b][c],solution(a-co[0],b-co[1],c-co[2])+1)
		return dp[a][b][c]
		

if __name__ == "__main__":
	N = int(input())
	scv = [0,0,0]
	arr = list(map(int,input().split()))
	for i in range(len(arr)):
		scv[i] = arr[i]
	answer = solution(scv[0],scv[1],scv[2])
	print(answer)

 

- BFS로 푸는 방법

# DFS로 풀 수 있으면 보통 BFS로 풀 수 있다. 그런데 BFS의 경우는 처음으로 정답 조건에 도달한 값이 최소성을 만족하므로, visited배열 대신 dp배열을 사용해서 활용 가능

# 큐엔 각각 scv 3개의 체력값, 지금까지 공격 횟수를 list로 저장한다.

#bfs로 풀기
import sys
from collections import deque
from itertools import permutations
INF = sys.maxsize

def solution(N,scv):
	q = deque()
	cur = [ scv[0],scv[1],scv[2],0]
	q.append(cur)
	perm = list(permutations([1,3,9],3))
	answer = 0
	dp = list(list([INF] * 61 for _ in range(61)) for _ in range(61))

	while q:
		cur = q.popleft()
		if cur[0] == 0 and cur[1] == 0 and cur[2] == 0:
			answer = cur[3]
			break

		else:
			for pe in perm:
				nex=[max(cur[0] - pe[0],0),max(cur[1]-pe[1],0),max(cur[2]-pe[2],0), cur[3] + 1]
				if dp[nex[0]][nex[1]][nex[2]] != INF:
					continue
				dp[nex[0]][nex[1]][nex[2]] = nex[3]
				q.append(nex)
	return answer

if __name__ == "__main__":
	N = int(input())
	scv = [0,0,0]
	tmp = list(map(int,input().split()))
	for i in range(len(tmp)):
		scv[i] = tmp[i]	
	answer = solution(N,scv)
	print(answer)

 

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

7. 행렬 곱셈 순서

- https://www.acmicpc.net/problem/11049

11049번: 행렬 곱셈 순서

- 문제 : 크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다. 행렬 N개의 크기가 주어졌을 때 모든 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값?

 

- 해결 방법: 유명한 문제!!!!

 #dp[i][j]: i번째~j번째 행렬까지 곱하는데 필요한 연산 횟수의 최솟값

 #dp[i][i] = 0이고, dp[i][i+1] = 직접 두개씩 곱하면 됨

 #dp[i][j] = dp[i][k] + dp[k+1][j] + arr[i][0]*arr[i+1][0] * arr[i+1][j] ---( i~k까지 곱하는 횟수) + (k+1~j까지 곱하는 횟수) + (두 행렬을 곱할하는 연산 횟수 )

import sys
input = sys.stdin.readline
INF = sys.maxsize
dp = []

def go(start,end):
	if start == end:
		return 0

	elif dp[start][end] != INF:
		return dp[start][end]
	
	else:
		for i in range(start,end):
			dp[start][end] = min( dp[start][end], go(start,i) + go(i+1,end) + arr[start][0]*arr[i+1][0]*arr[end][1])
		
		return dp[start][end]

if __name__ == "__main__":
	N = int(input())
	arr = list(tuple(map(int,input().split())) for _ in range(N))
	#dp[i][j]: i번째~j번째 행렬까지 곱하는데 필요한 연산 횟수의 최솟값
	dp = [[INF for _ in range(N)] for _ in range(N)] 
	
	#인접한 2개의 행렬은 미리 곱하기
	for i in range(N-1):
		dp[i][i+1] = arr[i][0]*arr[i+1][0]*arr[i+1][1]
		dp[i][i] = 0
	dp[N-1][N-1] = 0

	answer= go(0,N-1)
	print(answer)

 

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

8. 1,2,3 더하기 4

- https://www.acmicpc.net/problem/15989

15989번: 1, 2, 3 더하기 4

- 문제 : 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. ( 단, 2+1+1 1+1+2, 1+2+1 처럼 순서만 다른 경우는 같은 경우로 한다.

 

- 해결방법 : 중복 제거가 필요함. 따라서 2를 더할때와 3을 더할때를 독립적으로 취급해야 함!!!!!  

1) dp[i][j] : dp[i][j]: 1,2,3을 오름차순으로만 더할 때, 마지막으로 더할 수가 j이면서 합이 i인 경우의 수 

( https://torbjorn.tistory.com/289 글 ) 

MAX = 10001

if __name__ == "__main__": 
	answer = []
	dp = [[0,0,0,0] for _ in range(MAX)]
	dp[1][1] = 1 #1 
	dp[2][1] = 1 #1 1
	dp[2][2] = 1 # 2 
	dp[3][1] = 1 # 1 1 1 
	dp[3][2] = 1 # 1 2 
	dp[3][3] = 1 # 3

	for i in range(4,MAX):
		dp[i][1] = dp[i-1][1]# i-1에 1 더한 경우
		dp[i][2] = dp[i-2][1] + dp[i-2][2] # i-2에 2를 더한 경우
		dp[i][3] = dp[i-3][1] + dp[i-3][2]+ dp[i-3][3] #i-3에 3을 더한 경우 
		
	T = int(input())
	for _ in range(T):
		N = int(input())
		answer.append(sum(dp[N]))
	
	for x in answer:
		print(x)

 

2) dp[i] += dp[i-2] 를 다 돈 다음에, dp[i] += dp[i-3]을 더함!! (한번에 dp[i] = dp[i-2] + dp[i-3] 하면 중복 제거 x)

import sys
INF = sys.maxsize
MAX = 10001

if __name__ == "__main__": 
	answer = []
	dp = [1]* MAX
	
	for i in range(2,MAX):
		dp[i] += dp[i-2]
	
	for i in range(3,MAX):
		dp[i] += dp[i-3]
	
	T = int(input())
	for _ in range(T):
		N = int(input())
		answer.append(dp[N])
	
	for x in answer:
		print(x)

 

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

8. 기타리스트

- https://www.acmicpc.net/problem/1495

1495번: 기타리스트

- 문제 : N개의 음악을 연주하고, 각 연주 전 V[i]만큼  볼륨을 조절한다. 마지막 음악을 연주할 때 최대 볼륨값은?

- 해결방안:

# dp[i] :i번째a 음악까지 연주할때 가능한 볼륨의 개수를 딕셔너리로 저장

# 마지막 음악을 연주 못할 경우가 있을 수 있으므로, -1 처리 해야 함! 

# set인 list 초기화하는 법 : dp = list( set([-1]) for _ in range(N))

 

- 주의 사항:

#set은 add로 추가! ,discard로 삭제
#맨 첨에 dp를 defaultdict으로 해서 i가 생길때마다 값을 넣었더니 valueerror생김!!! 그냥 처음부터 메모리 할당하기

( https://www.daleseo.com/python-collections-defaultdict/) 

 

import sys
from collections import defaultdict
input = sys.stdin.readline
MAX = 101

if __name__ == "__main__":
	N,S,M = map(int,input().split())
	V = list(map(int,input().split()))
	V.insert(0,S)
	dp = [ set([-1]) for _ in range(MAX) ]
	dp[0].add(S)

	for i in range(1,N+1):
		for x in dp[i-1]:
			if x == -1:
				continue

			if x + V[i] <= M:
				dp[i].add(x + V[i])
			if x - V[i] >= 0:
				dp[i].add(x - V[i])
	print(max(dp[N]))

 

2) 다른 방법 :

 

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

9. 출근 기록

- https://www.acmicpc.net/problem/14238

14238번: 출근 기록

 

- 나중에 풀어볼 것

// https://nim-code.tistory.com/148 
#include <iostream>
#include <string>
using namespace std;

int worker[3];//0:A, 1:B, 2:C 입력받은 횟수 저장
bool DP[51][51][51][3][3] = { false, };//A기록 횟수, B기록 횟수, C기록 횟수, 이틀 전 기록, 어제 기록
char res[51];
string S;

bool solution(int a, int b, int c, int pp, int p) {
	if (a == worker[0] && b == worker[1] && c == worker[2])
		return true;
	//이미 구한 거
	if (DP[a][b][c][pp][p])return false;
	DP[a][b][c][pp][p] = true;

	if (a + 1 <= worker[0]) {
		res[a + b + c] = 'A';
		if (solution(a + 1, b, c, p, 0))
			return true;
	}
	if (b + 1 <= worker[1]) {
		res[a + b + c] = 'B';
		if (p != 1 && solution(a, b + 1, c, p, 1))
			return true;
	}
	if (c + 1 <= worker[2]) {
		res[a + b + c] = 'C';
		if (pp != 2 && p != 2 && solution(a, b, c + 1, p, 2))
			return true;
	}
	return false;
}

int main() {
	cin >> S;
	for (int i = 0; i < S.size(); i++) {
		if (S[i] == 'A')
			worker[0]++;
		else if (S[i] == 'B')
			worker[1]++;
		else
			worker[2]++;
	}
	if (solution(0, 0, 0, -1, -1))
		for (int i = 0; i < S.size(); i++)
			cout << res[i];
	else
		cout << -1;
	cout << '\n';
	
	return 0;
}

 

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

10. 두 동전

- https://www.acmicpc.net/problem/16197

16197번: 두 동전

- 문제: N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다.  두 동전의 위치는 다르다. 버튼을 누르면 두 동전이 버튼에 쓰여 있는 방향으로 동시에 이동하게 된다. 두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

 

- 해결방법:

#BFS로 큐 안에 두 동전의 위치, 버튼 누른 횟수를 저장

 

- 주의 사항:

# 큐엔 한 값만 넣어야 함. 그래서 여러 값을 넣으려면 list로 넣기
# 만약 큐 안에 여러 타입의 리스트 (ex, 좌표 리스트 + cnt )를 저장할 때 q.append([coins, 0]) 로 해야 함.q.append( arr + [cnt]) 하면 안됨
# break하는 문이 내가 원하는 거랑 맞는지 확인하기!!!!!!!1 난 while문을 나가고싶은데 안쪽의 for문에서 나갈수도 있음..바로 return하기
# 큐 값에서 꺼낼 때 cnt > 10이면 -1리턴하는 것 뿐만 아니라 if answer > 10일때도 answer = -1로 해야함ㅠㅜ

 

 

#16197 두 동전
# 보드에는 벽,빈공간이 있고 동전 2개가 있고. 버튼을 누를 때마다 두 동전은 같은 방향으로 한 칸이동한다. 두 동전중 하나만 보드에서 떨어뜨리기 위해 최소 몇 번 눌러야 하는지 출력 
# 큐엔 한 값만 넣어야 함. 그래서 여러 값을 넣으려면 list로 넣기
# 만약 큐 안에 여러 타입의 리스트 (ex, 좌표 리스트 + cnt )를 저장할 때 q.append([coins, 0]) 로 해야 함.q.append( arr + [cnt]) XX
# break하는 문이 내가 원하는 거랑 맞는지 확인하기!!!!!!!1 난 while문을 나가고싶은데 안쪽의 for문에서 나갈수도 있음..바로 return하기
# 큐 값에서 꺼낼 때 cnt > 10이면 -1리턴하는 것 뿐만 아니라 if answer > 10일때도 answer = -1로 해야함ㅠㅜ
import sys
from collections import deque
input = sys.stdin.readline

if __name__ == "__main__":
	dx = [-1,0,1,0]
	dy = [0,1,0,-1]
	
	N,M = map(int,input().split())
	arr = list(['.'] * M for _ in range(N))
	answer = -1
	coins = []
	visit = [[[[False] * M for _ in range(N)] for _ in range(M)] for _ in range(N)]
	
	for i in range(N):
		tmp = input()
		for j in range(M):
			if tmp[j] == 'o':
				coins.append([i,j])
			else:
				arr[i][j] = tmp[j]
	q = deque()
	q.append([coins, 0])
	visit[coins[0][0]][coins[0][1]][coins[1][0]][coins[1][1]] = True
	while q :
		cur = q.popleft()
		coin1 = cur[0][0]
		coin2 = cur[0][1]
		cnt = cur[1]
		if cnt > 10:
			break
		for k in range(4):
			nx1 = coin1[0] + dx[k]
			ny1 = coin1[1] + dy[k]
			nx2 = coin2[0] + dx[k]
			ny2 = coin2[1] + dy[k]
				
			# 둘 다 범위를 벗어난 경우 제외
			if (nx1 < 0 or nx1 >= N or ny1 < 0 or ny1 >= M) and (nx2 < 0 or nx2 >=N or ny2 < 0 or ny2 >=M):
				continue
			
			# 둘 다 범위 내에 있는 경우 이동 후 큐에 삽입 
			elif nx1 >= 0 and nx1 < N and ny1 >= 0 and ny1 < M and nx2 >= 0 and nx2 < N and ny2 >=0 and ny2< M:
				if arr[nx1][ny1] == '#':
					nx1 = coin1[0]
					ny1 = coin1[1]
					
				if arr[nx2][ny2] == '#':
					nx2 = coin2[0]
					ny2 = coin2[1]
				
				if visit[nx1][ny1][nx2][ny2] == False:
					visit[nx1][ny1][nx2][ny2] = True
					q.append([[[nx1,ny1],[nx2,ny2]], cnt+1])
			
			#둘 중 하나만 범위 내에 있는 경우 출력 
			else:
				answer = cnt + 1
				q.clear()
				if answer > 10:
					answer = -1
				break
	
	print(answer)

 

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

11. 크리보드 

- https://www.acmicpc.net/problem/11058

11058번: 크리보드

- 문제 : 크리보드늬 각 번호는 1(A출력), 2(ctrl-A) ,3 (ctrl-C) , 4(ctrl-v)의 4가지 버튼만 있다. 버튼을 N번 누를 때 출력할 수 있는 최대 A의 개수는?

 

- 해결방법:

# dp[i] : i번 버튼을 눌렀을때 A출력 횟수의 최댓값?

# dp[i] : dp[i-1] + 1(직전 값에 'A'를 추가한 값) 또는 dp[j]*(i-j-1) ( i-3 이하의 값을 버퍼에 담아서 붙여넣기 한 결과 )

# 혼자선 생각 못했던 문제.. (https://hjp845.tistory.com/139 , https://lemonlemon.tistory.com/156  참고)

 

-주의 사항:

# 난 처음에 dp[i]의 직전의 최댓값으로 수를 만들면 dp[i]도 최댓값이 될 거라고 생각했다..하지만 다음의 반례가 존재한다.

# N = 7일경우, 3번째에서 3을 버퍼에 담을 때 최댓값은 9가 된다. (3번째에 3, 4번째에 A, 5번째에 C, 6번째에 6(V), 7번째에(V) )

그렇지만 N = 10일 경우는 4를 버퍼에 담아야 최댓값이 되고, 이 과정에선 7번째 값은 8이어야 한다. ( 4번째에 4, 5번재에 A, 6번에 C, 7번에 8(V), 8번에 12(V), 9번에 16(V) ) 

 

#11058 크리보드
# 버튼 N을 눌러서 화면에 출력된 A개를 최대로 하는 프로그램 작성하라
# dp[i] = dp[i-1] + 1 (직전 값에 'A' 추가한 값) 또는, 이전값들을 버퍼에 담아서 ACVV...를 수행한 결과 중 큰 값
# 만약 dp[j]의 값을 buf에 넣는다면,j+1 인덱스부터 ACVVV..를 수행하여 dp[i]까지 값을 구할 수 있으며 그 값은 dp[j]*(i-j-1)일 것이다!

N = int(input())
dp = [0 for i in range(101)]

dp[1] = 1
dp[2] = 2

for i in range(3, 101):
    dp[i] = dp[i-1] + 1
    for j in range(i-3, -1, -1):
        dp[i] = max(dp[i], dp[j] * (i - j - 1))

print(dp[N])