[BOJ] 11052번 카드 구매하기 / 사용언어 : 파이썬(python)
※ 문제링크 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 해당문제는 동적프로그래밍과 관련된 문제로, 해결을 위해서는 점화식을 도출하는 것이 필수적이었다. 점화식을 도출하기 위해 가장 작은 단위부터 원리를 생각해봤을때, 카드팩을 1개살때는 P1을, 2개살때는 P1 + P1 과 P2중에 큰 값을, 3개 살때는 P1+P1+P1, P2 + P1, P3중 큰 값을 구하면 되었다. 즉, 구해야하는 카드의 수가 i일때, 1부터 i-1까지의 조합들의 값을 반복문을 통해 dp[i]에 저장된 값과 비교하여 큰 값으로 갱신하게끔 하면..
2022. 2. 20.
[BOJ] 14225번 부분수열의 합 / 사용언어 : 파이썬(python)
※ 문제링크 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 해당문제는 모든 경우의 수를 탐색해서 결과값을 확인하여 해결할 수 있는 문제였다. 다만, 숫자들의 조합에서 순서는 의미를 가지지않았기에 순열이 아닌 조합의 형태로 코드를 작성해야했다. 해당 조건을 고려하여 문제를 해결하였으며, 자세한 풀이방법과 코드는 아래와 같다. 1. 입력받은 값들을 리스트형태로 저장해준다. 2. 입력될 수 있는 리스트의 길이와 값을 바탕으로 방문여부를 확인할 리스..
2022. 2. 19.
