RUBY

출처:: 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)..

출처:: www.acmicpc.net/problem/2004 분류:: 수학 1. 문제 이해 및 해결과정 -n이 20억이다. 조합식으로 계산하는 코드를 만들었는데, 시간초과다 - 0이 생기는 경우를 고민해보면, 10은 즉, 2과 5의 곱으로 만들어진다 - 조합에서 0이 되려면 약분 후에 10의 배수(2*5)가 분자에 있으면 된다 - nCm = n! / m! (n-m)! 팩토리얼부분을 분자 A, 분모 B,C 라고 하면 A,B,C가 2로 나누어떨어지는 횟수를 구하여 A-(B+C)를 하고 , 5로 나누어 떨어지는 횟수를 A-(B+C) 를 하여 더 작은 값이 답이 된다. 2. 풀이방법 1. #조합 0의 개수 #https://www.acmicpc.net/problem/2004 import sys sys.stdin ..

출처:: www.acmicpc.net/problem/1373 분류:: 1. 문제 이해 및 해결과정 2. 풀이방법 1. #2진수 8진수 #https://www.acmicpc.net/problem/1373 import sys sys.stdin = open("input.txt","r") input=sys.stdin.readline print(oct(int(input(), 2))[2:]) #0x .... 3. 오답원인 4. 알게된 점 다른진수의 문자열을 숫자로 변환 int(str,2) #2진수의 문자열을 10진수 숫자로 int(str,8) #8진수의 문자열을 10진수 숫자로 int(str,16) #16진수의 문자열을 10진수 숫자로 숫자에서 다른진수의 문자열로 변환 bin(num) #숫자형 num을 2진수 문자..

출처:: www.acmicpc.net/problem/17103 분류:: 1. 문제 이해 및 해결과정 2. 풀이방법 #골드바흐 파티션 #https://www.acmicpc.net/problem/17103 import sys import math sys.stdin = open("input.txt","r") input=sys.stdin.readline t=int(input()) maxv= 1000000 sosu=[True]*(maxv+1) for i in range(2,int(math.sqrt(maxv))+1): #에라토스테네스의 체로 소수배열 구해두기 if sosu[i]: j=2 while i*jn-i: break if sosu[i]==True and sosu[n-i]==True: # 두 소수의 합 cnt+..