알고리즘(python) 검색 결과
179 개의 검색 결과가 있습니다.
알고리즘(python)/기본

[Python]동적계획법 백준 1463

문제 https://www.acmicpc.net/problem/1463 n번째에서 이전단계는 3개로 나뉜다.n-1번째의 최솟값 , 2로 나누어 진다면 n//2의 최솟값 , 3으로 나누어 진다면 n//3 의 최솟값이 셋중 작은것을 골라 1을 더해주게 되면 n번째의 최솟값을 구할수 있다. 12345678910111213141516171819202122n=int(input())result=[0 for _ in range(n+1)] def make_one(n): if n==1: return result[2]=1 if n==2: return result[3]=1 if n==3: return for i in range(4,n+1): result[i] = result[i - 1] + 1 if i%3==0: resul..

2020. 1. 9. 19:07
알고리즘(python)/기본

[Python]동적계획법 백준 2579

문제 https://www.acmicpc.net/problem/2579 마지막 계단을 무조건 밟아야 한다는 조건을 이용해보자.해당계단을 밟을때 최대값은 이전계단을 밟고 이전계단의 전전계단을 밟았을때와 전전계단을 밝을때 중 하나이다. 12345678910111213141516171819202122232425262728293031import sys n=int(sys.stdin.readline())steps=[]max_score=[0 for _ in range(n)]for i in range(n): steps.append(int(sys.stdin.readline())) def score(n): # 첫번째 계단 max_score[0]=steps[0] if n==1: return # 두번째 계단의 최대값은 두계단..

2020. 1. 9. 01:43
알고리즘(python)/기본

[Python]동적계획법 백준 1932

문제 https://www.acmicpc.net/problem/1932 양측의 위층합중 더큰 값을 선택하여 현재 층의 값과 더해주는 걸 반복해서 구하면 된다. 12345678910111213141516171819202122232425262728import sys n=int(input())triangle=[list(map(int,sys.stdin.readline().split())) for _ in range(n)]result=[]for i in range(1,n+1): result.append([0 for _ in range(i)]) #결과 담을곳 for i in range(n): if i==0: result[0][0]=triangle[0][0] else: for k in range(i+1): if k=..

2020. 1. 8. 23:27
알고리즘(python)/기본

[Python]동적계획법 백준 1149

문제 https://www.acmicpc.net/problem/1149 이전문제들보다는 조금 복잡한 형태가 될거같다.이웃과 같은색으로 칠할수 있다면 이전 최솟값에 집을 칠하는 비용의 최솟값을 더하면 간단히 구해질수 있지만 조건이 이웃과 같은 색을 칠할수 없다는 것에서 문제가 조금 복잡해 질거같다.코드로 구현하는게 어려웠다. 1234567891011121314151617181920212223242526import sys# 집의 수n = int(sys.stdin.readline())rgb_pay = [[0] * 3 for i in range(n)] for i in range(n): # 각 색별 페인트 비용 rgb_pay[i][0], rgb_pay[i][1], rgb_pay[i][2] = map(int, sy..

2020. 1. 8. 20:22
알고리즘(python)/기본

[Python]동적계획법 백준 9461

문제 https://www.acmicpc.net/problem/9461 수를 나열하기 보다는 위 그림을 보면 일정한 규칙을 볼수있다.P(n-5)와P(n-1)의변이 P(n)의 변을 이루는 모습을 볼수있다.코드로 짜보자 12345678910111213import sys n=int(sys.stdin.readline())padoban=[1 for i in range(101)]padoban[4]=2padoban[5]=2for i in range(6,101): padoban[i]=padoban[i-1]+padoban[i-5] while n>0: n-=1 print(padoban[int(sys.stdin.readline())])cs

2020. 1. 8. 11:15
알고리즘(python)/기본

[Python]동적계획법 백준 1904

문제https://www.acmicpc.net/problem/1904 이 문제의 규칙을 살펴보면n 수열1 12 11,003 100,111,0014 1100,0000,1001,1111,00115 10000,11100,00100,11001,00001,10011,11111,00111...n-2에 00을 붙이고 n-1에 1을 붙이면 n의 수열이 나오는것을 알수있다.수열의 개수로 계산했을경우 f(n)=f(n-1)+f(n-2) 피보나치의 형태와 같다. 나머지 계산이 아닌 일반적인 계산으로 1000000의 가짓수를 계산하면 컴퓨터가 멈추는 모습을 볼수있었다.... 1234567891011n=int(input()) tail_list=[0 for _ in range(n+1)]tail_list[1]=1if n>1: tai..

2020. 1. 8. 10:55