본문 바로가기
728x90

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

[BOJ/백준] 2193 이친수 ● [문제번호 2193] 이친수 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net ● 알아야 할 것 : 다이나믹 프로그래밍 : vector 자료구조와 메소드 ● 풀이 과정 : 하나씩 Bottom - Up 과정으로 작성해보니 규칙이 보였다. : 맨 앞자리에는 1이 오고 바로 그 다음자리에는 0이 와야만 한다. 그리고 그 다음자리부터는 index - 1 과 index - 2 의 방법의 갯수를 더한 것과 같다 1. 테이블 정의하기 → 각 i.. 2021. 7. 30.
[BOJ/백준] 10844 쉬운 계단 수 ● [문제번호 10844] 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net ● 알아야 할 것 : 다이나믹 프로그래밍 ● 풀이 과정 : 풀릴 듯 말 듯한 고민 끝에 구글링을 하였다. 코드를 보고 채점하고 풀이과정까지 작성해서야 완전히 이해했다. : 자릿수가 낮을 수록 높은 자리의 숫자를 의미한다. 예를 들어 자릿수가 5라면 자릿수 1에 있는 3은 34567과 같은 10,000단위의 숫자가 3이라는 뜻이다. 1. 테이블 정의 → 각 자릿수에서 1단위 수가 num인 경우의 계단 수의 총 갯수이다. 2. 점화식 찾기 → dp[digit][num] = .. 2021. 7. 30.
[BOJ/백준] 15990 1, 2, 3 더하기 5 ● [문제번호 15990] 1, 2, 3 더하기 5 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net ● 알아야 할 것 : 다이나믹 프로그래밍 : vector 자료구조와 메소드 ● 풀이 과정 : DP의 풀이과정 (Bottom-Up) 1. 테이블 정의하기 → end1 : index를 만드는데 마지막으로 추가한 숫자가 1인 경우 → end2 : index를 만드는데 마지막으로 추가한 숫자가 2인 경우 → end3 : index를 만드는데 마지막으로 추가한 숫자가 3인 경우 2. 점화식 찾기 → end.. 2021. 7. 30.
[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.
728x90

티스토리툴바