[백준][파이썬] 10844 쉬운 계단 수 DP는 결국 점화식을 찾고 점화식을 어떻게 배열에 저장해줄지 결정하면 된다. N = int(input()) #각 수마다 10개씩 값을 갖는다 dp = [[0 for i in range(10)] for j in range(101)] #첫 시행 초기화 for i in range(1,10): dp[1][i] = 1 #카운팅 0, 9,1~8 은 규칙이 다른것을 생각하자 for i in range(2,N+1): for j in range(10): if j == 0: dp[i][j] = dp[i-1][1] elif j == 9: dp[i][j] = dp[i-1][8] else: dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] print(sum(dp[N]) % 1000000000) https:/.. 2020. 7. 28. [백준][파이썬] 1,2,3 더하기 규칙을 찾는 연습을 잘하자.. 규칙을 논리적으로 찾을 수 있다면 좋다. 하지만 그것이 어려울 경우에는 무조건 숫자를 나열해보면서 찾는 것도 하나의 방법이다. case = int(input()) for _ in range(case): num = int(input()) numlist = [1,2,4] for i in range(3,num): tem = numlist[-1]+numlist[-2]+numlist[-3] numlist.append(tem) print(numlist[num-1]) 2020. 7. 21. [파이썬][알고리즘] 11727 2Xn 타일링 2 num = int(input()) numlist= [3,5] for i in range(2,num-1): tem1 = i-2 tem2 = i-1 tem = 2*numlist[tem1]+numlist[tem2] numlist.append(tem%10007) if num == 2: print(3) elif num == 1: print(1) else: print(numlist[-1]) 규칙을 이해하면 쉽다. 2020. 7. 21. [백준][파이썬] 11726 2Xn 타일링 num = int(input()) numlist= [2,3] for i in range(2,num-1): tem1 = i-2 tem2 = i-1 tem = numlist[tem1]+numlist[tem2] numlist.append(tem%10007) if num == 2: print(2) elif num == 1: print(0) else: print(numlist[-1]) 다이나믹 프로그래밍 문제이다. 피보나치 수열이지만, 문제를 보고 바로 피보나치 수열이라는것을 파악하진 못했다. 결국 다이나믹 프로그래밍 문제는 규칙을 찾는것이 중요하다. 메모리를 아끼려면, 리스트에 저장을 안하고 구해도 괜찮을것 같다. 중요한점은 10007을 매번 나눠주어야 한다는 것이다. num ==1일때 print(1)로 해야한다. 2020. 7. 21. [백준][파이썬] 1463번 1로 만들기 다이나믹 프로그래밍의 기본 문제다. 핵심은 "한번만 연산" 한다는 것이다. 탐색이나 bf 로도 풀 수 있겠지만 문제 특성상 반복되는 부분이 많고 이러한 반복되는 부분을 중복 계산 하지 않기 위해서 다이나믹 프로그래밍을 한다. cnt리스트에 100000을 붙인 이유는 나누기3 나누기2 마이너스1 중에서 해당사항이 없는 요소는 min에 값이 포함시키지 않기 위해서이다. 너무 오랜만에 파이썬으로 풀어서 문법이 헷갈릴 정도였다. 시험도 끝났으니 앞으로 매일 1~2문제씩은 꾸준히 열심히 푸는것을 목표로 해야겠다. num = int(input()) cnt = [100000] + [0 for i in range(num)] for i in range(2,num+1): div3 = 0 div2 = 0 if i % 3 =.. 2020. 7. 19. [백준][파이썬] 2206 벽 부수고 이동하기 - 메모리초과 BFS문제이지만 기존의 문제들과는 조금의 차이가 있다. 벽을 뚫을수 있다는 것을 체크해줘야한다. 1. 벽 뚫기를 위해 [x,y, 횟수] 이런식으로 저장을 해준다. 2. visited를 활용할때 주의할 점은 벽 안뚫기 / 벽 뚫었을때 따로 방문여부를 체크해줘야한다 (만약에 체크해주지 않으면, 벽뚫 vs 안뚫 이 만났을 때 오류가 생긴다 3. 메모리초과를 해결하지 못했다..... import sys import collections n, m = map(int,sys.stdin.readline().split()) map1 = [list(map(int,[*input()])) for k in range(n)] def recu(stack): stack.append([0,0,0]) cnt = 1 while stack.. 2020. 4. 13. [백준][파이썬] 16768 Mooyo Mooyo [핵심] 1. gravity함수 letsdel 함수 n, k = map(int,input().split()) map1 = [] for i in range(n): tt = list(input()) map1.append(tt) #str로 저장한거 기억하기 def gravity(map1): #중력 temto = [] temchange = [] for i in range(10): #열마다 tem = [] for j in range(n):#숫자저장 if map1[j][i] != "0": tem.append(map1[j][i]) for k in range(n-len(tem)): #뒤에 0채워주기 tem.insert(0,"0") temto.append(tem) for i in range(n): #행열 바꿔주기 tem.. 2020. 4. 8. [백준][파이썬] 3055번 탈출 -BFS 기본적인 BFS 문제에서 조금의 변형이 들어간 문제다. 처음 활용된 것은 물이라는 장애물도 퍼져나간다는것이다. 물 -> 길 ->물 ->길을 while안에서 활용했다 -항상 특정지점의 주변 모두를 한턴에 체크(FALSE)할때는 for(len(stack))구조로 활용해 주면 된다. -추가적으로 최단거리를 세기 위해서는 다른 리스트를 하나 더 만들어 수를 파악해주면 된다 import sys import collections n,m = map(int,input().split()) lit =[] ans =0 for i in range(n): tt = list(sys.stdin.readline()) lit.append(tt) dx = [0,0,1,-1] dy = [1,-1,0,0] def bfs(start,wate.. 2020. 4. 7. [백준][알고리즘] 14888 연산자 끼워넣기 def plus(a,b): return a+b def minus(a,b): return a-b def multi(a,b): return a*b def div(a,b): if a 이전 문제의 방식을 응용을 통해서 재귀함수가 상당히 깔끔해졌다. 리스트를 만드는 방식, enumerate 또한 적절히 잘 활용했다. num = int(input()) numlist = list(map(int,input().split())) calu = list(map(int,input().split())) mx = -10**9 mn = 10**9 # 가능한 조합 생성 하기 calu_t = calu[0] * "+" + calu[1] * "-" + calu[2] * "*" + calu[3] * "/" check = [False] * .. 2020. 4. 6. 이전 1 2 3 4 5 다음