백준/DP (67) 썸네일형 리스트형 백준 1754 - 진영 순열 icpc.me/1754 A[0]이 입력으로 주어진 이유 $A[0] \geq 0$ 인 순열들에 대해 진영 순열로 변환하면 다음과 같은 모양새를 띠게 된다. 0 _ _ _ ... / _ 0 _ _ ... / _ _ 0 _ ... / _ _ _ 0 ... 그러면 a + b = c라고 할 때 c-진영 순열이 되는 경우의 수는 0 왼쪽에 있는 순열이 a - 1 진영 순열인 경우 * 0 오른쪽에 있는 순열이 b-진영 순열인 경우 여기서 0 왼쪽에 있는 순열은 0때문에 기존 진영 순열에서 1 더해지므로 a - 1 진영 순열이어야 한다. A[0]인 경우도 따로 처리해야 한다. 이럴 때는 길이 n의 수열이 c-진영 순열인 경우를 구하면 된다. 진영 순열 구하기 기존에 순열에서 확장하는 것을 생각해보자. 다음 대소 관계를.. 백준 1086 - 박성원 icpc.me/1086 푸는 방법을 고민하기 전에... 어떤 큰 정수를 100 이하의 수로 나눈 나머지를 구하는 것은 어렵지 않다. 나눗셈을 손으로 푸는 과정을 구현하면 된다. 큰 정수를 스트링으로 받은 다음 반복문을 통해 (이전 자릿수까지 나눗셈을 통해 나온 나머지 * 10 + 현재 자릿수) % K 하면 된다. C계열 코드로는 다음과 같이 쓸 수 있겠다. 1 2 3 4 int pre = 0; for (int j = 0; j > k; for (int i = 0; i 백준 1351 - 무한 수열 noj.am/1351 P, Q가 최소 2이기에 N을 계속 쪼개는 과정은 지수적 감쇠를 생각하면 그렇게 많은 연산을 요하지 않음을 알 수 있다. 따라서 동적계획법을 통해 쪼개가면서 얻은 값을 저장하면 빠르게 풀 수 있을텐데 문제는 N의 범위가 커서 배열로 저장을 할 수 없다는 것이다. 이를 해결하기 위해 map을 사용하여 값을 저장하면 필요한 값만 메모리를 사용하기 때문에 메모리 할당에 문제 없이 문제를 풀 수 있다. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include #include using namespace std; using ll = long long; unordered_map dp; ll n, p,.. [POI] 백준 2287 - 모노디지털 표현 noj.am/2287 분석과 아이디어 본문에 자연수 X를 몇 개의 숫자 k와 사칙연산을 통해 표현한다고 되어있다. 설명에서 5는 1, 55는 2 임을 발견할 수 있고 숫자를 몇 개 이어 붙였는지로 표현 길이를 결정했음을 알 수 있다. 그러면 우리는 어떻게 표현 길이를 최소화시킬 수 있을까? 설명에 나열된 표현식들을 보면 중복될 수 있는 경우도 분명 있을 것이고 거기에 괄호도 고려해야 하기 때문에 상당히 어려워 보인다. 하지만 표현의 결과는 식도 아니고 값이다. k와 연산자들을 어떻게 섞었든 그 결과는 값으로 존재한다. 표현의 결과로 a와 b가 있다면 a (*, /, +, -) b 꼴로 c가 계산될 것이며, c의 표현 길이는 a를 만들기 위한 표현 길이 + b를 만들기 위한 표현 길이가 된다. 우리는 이렇.. [ICPC] 백준 2066 - 카드놀이 www.acmicpc.net/problem/2066 문제 소개 원문은 Double patience라는 게임을 하는데 규칙을 따르면서 랜덤 픽하는 조지가 그게 효율적이지 않다고 까는 매튜와 논쟁을 벌이면서 이 게임을 이길 수 있는 확률을 구하는 것이다. 풀이 놀랍게도 구차원 dp이다. 테이블은 다음과 같다. dp[a][b]...[h][i] := 각 묶음에서 카드가 a장, b장, ... h장, i장 있을 수 있는 확률 dp[4][4][4][4][4][4][4][4][4]는 카드가 모두 쌓여있는 초기 상태이기 때문에 1.0으로 두면 된다. 카드가 4장씩 9묶음만 있기 때문에 9중첩 반복문을 돌려도 실행 시간이 여유로움을 알 수 있다. 카드가 모두 쌓여있는 경우부터 시작해서 규칙에 맞게 카드를 제거할 수 있는 .. 이전 1 ··· 5 6 7 8 9 10 11 ··· 14 다음
