RUBY

출처:: www.acmicpc.net/problem/1699 분류:: dp 1. 문제 이해 및 해결과정 - dp : i를 표현할 수 있는 제곱수의 합의 최소 개수 1 1 2 2 3 3 4 1 5 2(4+1) 6 3(4+1+1) 7 4(4+1+1+1) 8 2(4+4) 9 1(9) 10 2(9+1) 11 3(9+1+1) 12 3(4+4+4) 2. 풀이방법 1. [python] dp #제곱수의 합 #https://www.acmicpc.net/problem/1699 import sys import math sys.stdin = open("input.txt","r") n=int(input()) dp=[0]*(n+1) for i in range(1,n+1): dp[i]=i for j in range(1,i): if..

출처:: www.acmicpc.net/problem/1149 분류:: dp 1. 문제 이해 및 해결과정 - 각 열에서 한 개씩 선택해서 단, 색상조건 고려해야함 - i가 빨강으로 칠해질때, i-1에는 초록이나 파랑 칠해져 있어야한다. - i가 파랑으로 칠해질때, i-1에는 초록이나 빨강 칠해져 있어야한다. - i가 초록으로 칠해질때, i-1에는 빨강이나 파랑 칠해져 있어야한다. dp[i][j] : 집i번까지 j색으로 칠했을 때 최소비용 => dp[i][r] = min(dp[i-1][g], dp[i-1][b]) + cost[i][r] ,g,b도 이와 같다 0 1 2 번 집 빨간색으로 칠해질 때, 26 40 83 초록색으로 칠해질 때, 49 60 57 파랑색으로 칠해질 때, 13 89 99 26 40 83 ..

출처:: www.acmicpc.net/problem/2193 분류:: dp 1. 문제 이해 및 해결과정 1) 자리수별로 풀이 1자리 일때 , 1 2, 10 3, 100 101, 4, 1000 1001 1010 5, 10000,10001,10010,10100,10101 끝자리가 1이면 0만 가능 끝자리가 0이면 , 0과 1 가능 0으로 끝나는 것 1로 끝나는 것 1 0 1 2 1 0 3 1 1 4 1+1 1 5 dp[n][2] dp[i][j]=길이가 i이고 j로 끝나는 것의 개수 dp[i][0]=dp[i-1][0]+dp[i-1][1] dp[i][1]=dp[i-1][0] 2) 규칙 - dp[i]=dp[i-1]+dp[i-2] 규칙을 찾을 수 있다. 2. 풀이방법 1. [python] dp #이친수 #https..

출처:: www.acmicpc.net/problem/1912 분류:: dp 1. 문제 이해 및 해결과정 - 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 1) 10까지, 10 2) -4까지, 6 (10, 10-4) 3) 3까지, 10-4+3, -4+3, 3 = 9, -1, 3 4) 1까지,10-4+3+1, -4+3+1, 3+1, 1 = 10,0,4,1 => dp[i]=max(dp[i],dp[i-1]+arr[i]) dp= [10, 6, 9, 10, 15, 21, 0, 12, 33, 32] 2. 풀이방법 1. [python] dp #연속합 #https://www.acmicpc.net/problem/1912 import sys sys.stdin = open("input.txt","r") in..

출처:: www.acmicpc.net/problem/14002 분류:: dp 1. 문제 이해 및 해결과정 - dp[i]=arr[i]까지 수 중 가장 긴 증가하는 부분수열 A = {10, 20, 10, 30, 20, 50} 1) 10까지, 1개 2) 20까지, max( dp[i-1] + if 10>20 +1 , 1) 3) 10까지 , max( dp[i-1] -> 2개, 1(자기자신)) 4) 30까지, max( dp[i-1] + dp의 최대값보다 크다면 2. 풀이방법 1. [python] dp #가장 긴 증가하는 부분 수열 4 #https://www.acmicpc.net/problem/14002 import sys sys.stdin = open("input.txt","r") input=sys.stdin.re..

출처:: www.acmicpc.net/problem/2309 분류:: 브루트포스 1. 문제 이해 및 해결과정 2. 풀이방법 1. python #일곱 난쟁이 #https://www.acmicpc.net/problem/2309 import sys from itertools import combinations sys.stdin = open("input.txt","r") nan=list(int(input()) for _ in range(9)) selected=list(combinations(nan,7)) for i in range(len(selected)): if sum(selected[i])==100: res=list(selected[i]) res.sort() for x in res: print(x) exit..

출처:: https://www.acmicpc.net/problem/1748 분류:: 브루틀포스 1. 문제 이해 및 해결과정 2) - 1 ~9 => 9개 - 10 ~99 => 90개 - 100 ~999 => 900개 - 그 전 자리수의 합 + 현재자리수 n-i+1 2. 풀이방법 1. python #수 이어 쓰기 1 #https://www.acmicpc.net/problem/1748 import sys sys.stdin = open("input.txt","r") input=sys.stdin.readline n=int(input()) cnt=0 for i in range(1,n+1): cnt+=len(str(i)) print(cnt) 2. python 시간 개선 #수 이어 쓰기 1 #https://www.ac..

출처:: www.acmicpc.net/problem/10844 분류:: dp 1. 문제 이해 및 해결과정 - dp[i][j] = 길이가 i일때 , 끝자리가 j일 경우 계단 수의 개수 - 0은 계단수가 아니다 j 0 1 2 3 4 5 6 7 8 9 dp[1] 0 1 1 1 1 1 1 1 1 1 dp[2] 1 1 2 2 2 2 2 2 2 1 ex)dp[2][0] = 길이가 2일때, 끝자리가 0인 수의 개수 =>1개, 10 dp[3] 1 3 3 4 4 4 4 4 3 2 ex) dp[3][2] = 길이가 3일때, 끝자리가 2인 것의 개수 =>3개, 132 212 232 - dp[3][2] 를 보면, 끝자리가 2일 경우 가능한 앞자리는 1 과 3이다. 길이가 2이면서, 끝자리가 1과 3 인경우는 각각 1개(21)..