반응형
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- Iceberg
- 코딩테스트
- 코엑스
- 삼성역맛집
- apache iceberg
- 맛집
- BigData
- 알고리즘
- bigdata engineer
- Data Engineer
- pyspark
- 코딩
- Data Engineering
- Spark
- 용인맛집
- Trino
- 개발
- hadoop
- 여행
- 자바
- Apache Kafka
- bigdata engineering
- 영어
- 프로그래머스
- 코엑스맛집
- HIVE
- Kafka
- 백준
- 코테
- java
Archives
- Today
- Total
지구정복
[DP] 백준 - 카드 구매하기 2 본문
728x90
반응형
-자바
package dp;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class BuyingCard2 {
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
private static int n;
private static int[] p;
private static int[] d;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt( br.readLine() );
p = new int[n+1]; //카드팩의 가격
d = new int[n+1]; //dp배열
StringTokenizer st = new StringTokenizer( br.readLine() );
for( int i=1; i<=n; i++ ) p[i] = Integer.parseInt( st.nextToken() );
d = new int[n+1];
for( int i=2; i<=n; i++ ) d[i] = 10001;
d[1] = p[1];
for( int i=2; i<=n; i++ ) {
for( int j=0; j<i; j++ ) {
d[i] = Math.min( d[i], d[j]+p[i-j] );
}
}
bw.write( d[n] + "\n" );
bw.flush();
bw.close();
br.close();
}
}
-파이썬
n = int( input() )
p = [0] + list( map( int, input().split() ) )
d = [10001] * (n+1)
d[0] = 0
d[1] = 1
for i in range( 2, n+1 ):
for j in range( 0, i ):
d[i] = min( d[i], d[j]+p[i-j] )
print( d[n] )
728x90
반응형
'데이터 엔지니어링 정복 > Algorithm' 카테고리의 다른 글
[DP] 백준 - 가장 긴 감소하는 부분수열 (0) | 2021.07.14 |
---|---|
[DP] 백준 - 1,2,3 더하기 5 (0) | 2021.07.14 |
[DP] 백준 - 2Xn 타일링 (0) | 2021.07.13 |
[DP] 백준 - 카드 구매하기 (0) | 2021.07.13 |
[DP] 이코테 - 호율적인 화폐구성 (0) | 2021.07.13 |
Comments