본문 바로가기
[백준][파이썬] 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.
[백준][파이썬] 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.
[파이썬][백준] 2448 번 별찍기 (11) [핵심] 별찍기(10)이랑 거의 동일한 문제지만 x,y좌표값이 일정하지 않고 출력형식에 맞춰주기만 하면 동일한 유형이 된다. num = int(input()) tnum = 2*num -1 lit =[[" " for i in range(tnum)] for j in range(num)] def recu(x,y,cnt,num): if cnt == 5: for i in range(x,x+3): for j in range(y,y+5): if i == x and j == y+2: lit[i][j] = "*" if i == x+1 and j == y+1: lit[i][j] = "*" if i == x+1 and j == y+3: lit[i][j] = "*" if i == x+2: lit[i][j]="*" return.. 2020. 3. 22.
[백준][파이썬] 2447번 별찍기 [핵심] 분할정복을 이용한 별찍기 문제이다. 분할정복을 좌표를 활용하여 문제를 문때는 항상 시작점을 (0,0)이 아닌 넘겨받은(X,Y)로 해야한다. -> 자꾸 실수함. num = int(input()) lit =[["" for i in range(num)] for j in range(num)] def recu(x,y,tf,cnt): if cnt == 3: for i in range(x,x+3): for j in range(y,y+3): lit[i][j] = "*" if i == x+1: if j == y+1: lit[i][j] = " " return else: cnt = cnt // 3 recu(x, y, tf,cnt) recu(x, y+1*cnt, tf, cnt) recu(x, y+2*cnt, tf, .. 2020. 3. 22.

티스토리툴바