Algorithm/Dynamic Programming69 [파이썬] 백준 21317 : 징검다리 건너기 (실버1) [파이썬] 백준 21317 : 징검다리 건너기 (실버1) 21317번: 징검다리 건너기 산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다. www.acmicpc.net 문제 풀이 0. 방향성 생각 단방향으로 상태가 나누어져있는 DP. 2차원 DP로 만들거나, DP배열을 두 개 만든다. dp0에서 슈퍼점프(2칸 건너뛰는 점프)를 하면 dp1로 이동하는 방식으로 풀었다. 1. 입력 n = int(input()) info = [[0,0]] for _ in range(n-1): info.append(list(map(int,input().split()))) superjump = int(input()) 첫 번째 돌 부터 출발하므로 인덱스를 맞추기 위해서 더미 [0,0]를 info에 넣는다. info[i번째 돌.. 2023. 7. 30. [파이썬] 백준 2670 : 연속부분최대곱 (실버4) [파이썬] 백준 2670 : 연속부분최대곱 (실버4) 2670번: 연속부분최대곱 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 www.acmicpc.net 문제 풀이 방향성 생각 1차원 DP를 만든다. 초기값은 arr의 첫 번째 값. 두 번째 값부터는 arr[i+1]과 dp[i]*arr[i+1] 값을 비교해준다. 큰 것을 DP에 할당 전체코드 n = int(input()) arr = [float(input()) for _ in range(n)] dp = [0]*n dp[0] = arr[0] for i in range(n-1): dp[i+1] = ma.. 2023. 7. 30. [파이썬] 백준 11057 : 오르막 수 (실버1) [파이썬] 백준 11057 : 오르막 수 (실버1) 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 문제 풀이 방향성 생각 2차원 dp 배열을 만들준다. 0부터 시작할 수 있으니 모든 시작점을 1로 초기화한다. 마지막 숫자가 n보다 같거나 큰 숫자들은 모두 등장할 수 있다. 0보다 같거나 작은 수라 생각해도 무방하다 (대칭형) dp[자리수][선택한 숫자] = sum(dp[이전 자리수][0부터 선택한 숫자까지])%k 전체 코드 n = int(input()) dp = [[0]*1.. 2023. 7. 30. [파이썬] 백준 2156 : 포도주 시식 (실버1) [파이썬] 백준 2156 : 포도주 시식 (실버1) 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 풀이 방향성 생각 arr에 포도주를 순서대로 넣는다. 상태는 3가지가 존재한다. 선택하지 않은 상태 / 연달아 1개를 선택한 상태 / 연달아 2개를 선택한 상태. dp 배열을 3xn으로 만든다. DP 배열의 시작은 각각 0, arr[0], 0으로 초기화한다. 배열의 첫번째에는 이전에 선택하지 않거나 연달아 두 개 선택한 경우는 없음. dp[0][i+1] : 현재 포도주를 선택하지 않는 경우 -> 연달아서 선.. 2023. 7. 24. 이전 1 ··· 12 13 14 15 16 17 18 다음
