본문 바로가기
반응형

알고리즘/dynamic programming27

[프로그래머스][Python] 등굣길 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움.. 2023. 2. 8.
[프로그래머스][Python] 정수 삼각형 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상.. 2023. 2. 6.
[백준][Python] 15988번 1, 2, 3 더하기 3 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 코드 import sys t = int(input()) dp = [0,1,2,4] for _ in range(t): n = int(sys.stdin.readline()) for i in range(len(dp),n+1): dp.append((dp[i-3]+dp[i-2]+dp[i-1])%1000000009) print(dp[n]) 설명 처음에는 for문 안에 dp를 선언해서 새로운 n 값을 받을 때마다 dp 계산을 했더니 시간초과가 떴다. 그래서 dp를 만들어놓고 계속해서 그 값을 가져다 쓰는 방식으로 다시 코드를 .. 2022. 12. 29.
[백준][Python] 16194번 카드 구매하기2 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 코드 n = int(input()) p = list(map(int,input().split())) dp = [0]*(n+1) dp[1] = p[0] dp[2] = min(dp[1]*2,p[1]) for i in range(3,n+1): dp[i] = p[i-1] for j in range(1,i//2+1): dp[i] = min(dp[i],dp[j]+dp[i-j]) print(dp[-1]) 2022. 12. 27.
반응형

티스토리툴바