본문 바로가기
728x90

Baekjoon/[Code.plus] 알고리즘 기초 1／269

[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.
728x90

티스토리툴바