백준 (227) 썸네일형 리스트형 백준 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중첩 반복문을 돌려도 실행 시간이 여유로움을 알 수 있다. 카드가 모두 쌓여있는 경우부터 시작해서 규칙에 맞게 카드를 제거할 수 있는 .. 백준 1480 - 보석 모으기 icpc.me/1480 솔루션 - 이차원 DP 더보기 테이블을 다음과 같이 정의한다. dp[i][j] := i번째 가방까지 보석의 조합을 비트마스크로 표현한 j로 채우는게 가능한가? 첫번째 가방에 보석을 채울 수 있는 경우를 비트마스크로 확인하고 다음 가방에 다른 보석을 넣는 경우를 계산한 후 m번째 가방까지 썼을 때 최대 비트를 구해 출력하면 된다. 전체 코드 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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68.. 이전 1 ··· 30 31 32 33 34 35 36 ··· 46 다음 33/46
