본문 바로가기
728x90

전체 글205

[BOJ/백준] 16194 카드 구매하기 2 ● [문제번호 16194] 카드 구매하기 2 https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net ● 알아야 할 것 : 다이나믹 프로그래밍 : vector 자료구조와 메소드 ● 풀이 과정 : 이전에 풀었던 [11052 카드 구매하기] 문제에서 max → min 으로 변경하기만 하면 된다. 1. 테이블 정의 → 각 index의 값은 카드 index개를 갖기 위해 지불해야 하는 금액의 최솟값을 나타낸다. 2. 점화식 찾기 → dp[i] = min(dp[i .. 2021. 7. 30.
[BOJ/백준] 11052 카드 구매하기 ● [문제번호 11052] 카드 구매하기 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net ● 알아야 할 것 : 다이나믹 프로그래밍 : vector 자료구조와 메소드 ● 풀이 과정 : 점화식을 찾을 듯 말 듯한 고통 속에 결국 구글링을 했다. 뭔가 예전에 이러한 방식과 비슷한 문제를 본 것 같은데 다음에 다시 만나게 되면 풀 수 있도록 연습해 둬야겠다. 1. 테이블 정의 → 각 index의 값은 카드 index개를 갖기 위해 지불해야 하는 금액의 최댓값.. 2021. 7. 30.
[BOJ/백준] 9095 1, 2, 3 더하기 ● [문제번호 9095] 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net ● 알아야 할 것 : 다이나믹 프로그래밍 : vector 자료구조와 메소드 ● 풀이 과정 : DP의 풀이과정 (Bottom - Up) 1. 테이블 정의하기 → 각 index의 값은 1, 2, 3의 합으로 나타내는 방법의 수를 나타낸다. 2. 점화식 찾기 → dp[index] = dp[index - 1] + dp[index - 2] + dp[index - 3] dp[index]는 dp[index - 1] 에서 구한 각 방법에 1을 추가하면 되는 것과 .. 2021. 7. 30.
[BOJ/백준] 11727 2×n 타일링 2 ● [문제번호 11727] 2×n 타일링 2 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net ● 알아야 할 것 : [BOJ/백준] 11726 2×n 타일링 : 다이나믹 프로그래밍 : vector 자료구조와 메소드 ● 풀이 과정 : (이전 문제) [BOJ/백준] 11726 2×n 타일링 를 풀어봤다면 1줄의 코드만 수정하여 해결할 수 있다. : 2×2 타일이 추가되었는데 이것은 1×2 타일 2개와 똑같다. : DP의 풀이과정 (Bottom - Up) 1. 테이블 정의하기 → .. 2021. 7. 30.
[BOJ/백준] 11726 2×n 타일링 ● [문제번호 11726] 2×n 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net ● 알아야 할 것 : 다이나믹 프로그래밍 : vector 자료구조와 메소드 ● 풀이 과정 : DP의 풀이과정 (Bottom - Up) 1. 테이블 정의하기 → 각 index의 값은 '2×index의 타일로 채우는 방법의 수'를 나타낸다. 2. 점화식 찾기 → dp[index] = dp[index - 1] + dp[index - 2] 2×1 타일 1개 추가하면 되는 경우 = dp.. 2021. 7. 30.
[BOJ/백준] 1463 1로 만들기 ● [문제번호 1463] 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net ● 알아야 할 것 : 다이나믹 프로그래밍 ● 풀이 과정 : 재귀로만 모든 경우 확인하는 방법으로 구현했더니 '시간 초과' 결과가 나왔다. 2로 나눈 나머지와 3으로 나눈 나머지를 비교하여 재귀하는 방법으로 시간을 단축시킬려고 했으나 이번에 답이 옳지 않게 나왔다. 결국에 구글링을 하였다. : 참고 링크에 해당 문제를 Top - Down 방식과 Bottom - Up 방식으로 모두 풀이 되어 있다. : 아래 코드는 Top - Down 방식으로 구현하였다. (Bottom - Up.. 2021. 7. 30.
728x90