[SWEA] 19189 순열의 아름다움
2024. 1. 22. 21:03
Algorithm/DP
문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AYzIcBsq_agDFAQ9&categoryId=AYzIcBsq_agDFAQ9&categoryType=CODE&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 접근 여러 가지 접근이 있는데 필자가 접근한 단계로 차근차근 진행해 보도록 하겠다. BruteForce 구현 모든 경우의 수를 구해야 하는데... 문제를 보면 $1 \leq N \leq 250000$ 이다. 우리가 찾는 아름다운 쌍을 찾기 위해서는 먼저 $250000!$ 개의 행들을 훑어야 하는데 당연히 시..
[백준][BOJ 2502] - 떡 먹는 호랑이
2023. 10. 2. 19:07
Algorithm/DP
문제 https://www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 문제 접근 점화식이 이미 문제에서 주어져 있다. 점화식은 다음과 같이 주어진다. $A_k = A_{k - 1} + A_{k - 2}$ 문제에서 요구하는 답은 특정 시점과 떡의 개수가 주어질 때 초기값을 구하라는 것이다. 이때 문제 조건에서 항상 $A_1 \leq A_2$를 만족한다는 것을 유의하라 $A_1$은 특정 시점에 주어진 떡의 개수를 $K$라고 할 때 $K/2$까지 될 수 있..
[BOJ 2193] 백준 2193 이친수
2022. 12. 1. 14:03
Algorithm/DP
문제 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 접근 조건 기본적인 dp 문제이다. dp 테이블을 정하자 이때 dp[i]를 길이 i일 때 가질 수 있는 이친수의 가짓수로 정의할 것이다. 이친수의 조건에 따라 길이 1, 2일때의 이친수는 각각 1, 10으로 1개씩이 될 것이다. 길이 3이후의 이친수의 가짓수를 살펴보면 다음과 같다. 3일때 가질 수 있는 이친수는 101, 100으로 2가지이다. 4일때 가질 수 있는 이친수는 101..