반응형 백준알고리즘/동적 계획법175 (Python/🥈4)백준 알고리즘 1463번: 1로 만들기 문제 바로가기 문제: 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력: 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력: 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 풀이 : 이 문제는 dp 를 사용하는 문제이다. 나는 포문을 이용한 바텀업 방식이 더 익숙하고 처음 두 수를 알수 있어 상향식인 바텀업으로 풀었다 처음에는 그리디를 생각할 수 있지만 10인경우에 -1 을 먼저 하는 경우가 유리하기 때문에 불가능하다. 점.. 2023. 6. 12. (Python/🥈3) 백준 알고리즘 2579번: 계단 오르기 문제 출처: https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이: 1. import sys sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r') N = int(input()) dp = [0] * 301 arr = [0]*301 for i in range(N): arr[i] = int(input()) dp[0] = arr[0] dp[1] = arr[0] + arr[1] dp[2] = max(ar.. 2022. 11. 14. (Python/🥈1)백준 알고리즘 1932번: 정수 삼각형 문제 출처;https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이: import sys sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r') def solution(triangle): dp = [[0]*len(triangle) for i in range(len(triangle))] dp[0][0] = triangle[0][0] for i in range(0, len(triangle)-1): for j in range(len(triangle[i])): dp[.. 2022. 11. 14. (Python/🥈1)백준알고리즘 1149번: RGB거리 문제 출처: 문제 풀이: import sys sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r') n = int(input()) RGB = [] for i in range(n): RGB.append(list(map(int,(input().split())))) for i in range(1,len(RGB)): RGB[i][0] = min(RGB[i - 1][1], RGB[i - 1][2]) + RGB[i][0] RGB[i][1] = min(RGB[i - 1][0], RGB[i - 1][2]) + RGB[i][1] RGB[i][2] = min(RGB[i - 1][0], RGB[i - 1][1]) + RGB[i][2] print(min(RGB[-1.. 2022. 11. 13. (Python/🥈2)1912번: 연속합 문제 출처: https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이: import sys n = int(input()) lst = list(map(int,(input().split(' ')))) for i in range(1, n): lst[i] = max(lst[i], lst[i] + lst[i-1]) print(max(lst)) lst[i] = max(lst[i], lst[i] + lst[i-1] lst[i] 이전까지 계산해온 값중 최댓값을 계속저장함 .. 2022. 11. 13. (Python/🥈3)9461번: 파도반 수열 문제 출처: https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이: n = int(input()) def dp(n): dp = [0] * 101 dp[1],dp[2] = 1, 1 for i in range(3, n+1): dp[i] = dp[i-3] + dp[i-2] return dp[n] for i in range(n): number = int(input()) print(dp(number)) 2022. 11. 13. 이전 1 ··· 9 10 11 12 13 다음 반응형
