생각 생각

https://acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 점화식이 잘 안 떠올라서 성가셨다. n = int(input()) dp = [0 for _ in range(31)] dp[2] = 3 for i in range(4,n+1,2) : # 어차피 홀수는 만들 수가 없다. if i%2 == 0 : # 핵심은 2*3 이상의 블록, 즉 4*3, 6*3 등의 블록은 두 개만 만들 수 있다는 것. dp[i] = dp[i-2] * 3 + sum(dp[:i-2]) * 2 + 2 print(dp[n])

https://acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 더 좋은 풀이가 있는데, 생각이 잘 안나서 직관적으로 풀었다. 오래 걸리고 별로인 풀이. import sys input=sys.stdin.readline N,K=map(int,input().split()) # 숫자를 받아 enumerate 하고 큰 수부터 확인할 것이다. nums=[(v,i) for i,v in enumerate(list(input().strip()))] nums.sort(key=lambda x:(-int(x[0]))) ans=[False]*(N-K) f=0 # f..

https://acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 간단한 다익스트라 문제. 10분정도 걸려서 원트클. import sys, heapq input=sys.stdin.readline m,n=map(int,input().split()) INF=10001 # 최장 거리로 돌아가도 10000이므로 10001이면 충분하다. graph=[] dis=[[INF]*m for _ in range(n)] #distance 초기값을 INF로 둔다. q=..

https://acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 전혀 안 어려운 문제인 줄 알았는데, '같은 무게의 공은 먹을 수 없다'는 조건때문에 어려웠던 문제. 골드 2가 적정 난이도라는 생각이 들 만큼 까다로웠다. import sys input=sys.stdin.readline N=int(input()) # balls에는 가치별로 공을 넣는다. 일종의 sorting인데, 같은 가치의 공을 처리하기 위함이다. # d에는 특정 색깔의 ..

https://acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 2293과 비슷한 듯 다른 듯한 맛. n,k=map(int,input().split()) coins=[int(input()) for _ in range(n)] # dp에는 특정 value를 만들 수 있는 최소 동전의 개수를 넣는다. # 동전은 10000개까지 이용할 수 있으니 초기값은 10001개로 충분하다. dp=[10001]*(k+1) dp[0]=0 # dp[동전]=1을..

https://acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 소마 대비를 위한 dp 연습. n,k=map(int,input().split()) coins=[0]*n for i in range(n): coins[i]=int(input()) # dp 배열에는 가치의 합이 특정 값인 경우의 수가 들어간다. dp=[0]*(k+1) # 이 dp[0]=1은 이후 업데이트시 dp[동전]+=dp[동전-동전]을 위한 것이다. # 즉, 특정 동전 하나를 써서 value를 올릴 수 있..

https://acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 1600과 동일하다. 부순 벽의 개수를 기록해두자. Python3로는 풀 수 없다. pypy3만 가능하니 참고하도록 하자. from collections import deque import sys input=sys.stdin.readline INF=sys.maxsize N,M,K=map(int,input().split()) dy=[1,-1,0,0] dx=[0,0,1,-..

https://acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net from collections import deque import sys input=sys.stdin.readline INF=sys.maxsize K=int(input()) W,H=map(int,input().split()) # 말 무빙과 원숭이 무빙 배열 dy_h=[1,2,2,1,-1,-2,-2,-1] dx_h=[-2,-1,1,2,2,1,-1,-2] dy_m=[1,-1,0,0] dx_m..