혼새미로의 블로그

주어진 알고리즘을 직관적으로 생각하기 어렵다고 생각하여 문제를 4개의 작은 문제들로 분리해보았습니다.먼저, 원본 문제의 링크입니다: https://algospot.com/judge/problem/read/ZIMBABWE입력받은 양의 정수형 숫자 num에 대하여 각 자릿수의 숫자 순서를 바꾸어 나타낼 수 있는 모든 값들 중에서 num보다 작은 값을 갖고, 또 다른 주어진 입력 값 M의 배수인 값들을 모두 출력하라. 단, 자릿수들의 값은 서로 같을 수 있으며, (예: 2031, 4401, 5550016, 10348 등이 num으로 가질 수 있다), 2

분해2에서 설명했듯이, 가장 큰 자릿수의 숫자부터 순서대로 선택할 때, 만약 i번째 까지 선택된 숫자들이 동일하다면, (예를들어, num=2030 일때, 앞에 20이 선택되었든 02가 선택되었든) 이후에 선택되어 나열될 수 있는 경우의 수는 동일합니다. (20->2003,2030...02->0203,0230) 따라서, 선택된 값 (예:02)들을 인덱스로 해서 가능한 나열의 수를 최초로 계산한 결과를 보관해두면, 나중에 같은 값(예:20)을 선택했을 때, 같은 인덱스를 참조하여 별도의 반복문 없이 빠르게 값을 얻을 수 있습니다. 같은 숫자들의 집합에 대하여 같은 인덱스를 가지도록 하기 위해 다음과 같은 방법을 사용할 수 있습니다. n자리 숫자에 대하여 i번째 자릿수의 숫자를 선택했다고 하면 i번째 비트 값..

주어진 알고리즘을 직관적으로 생각하기 어렵다고 생각하여 문제를 4개의 작은 문제들로 분리해보았습니다. 먼저, 원본 문제의 링크입니다: https://algospot.com/judge/problem/read/ZIMBABWE 입력받은 양의 정수형 숫자 num에 대하여 각 자릿수의 숫자의 순서를 바꾸어 나타낼 수 있는 모든 경우의 수를 출력하라. 단, num의 각 자릿수의 숫자는 중복될 수 있다. (예: 123, 385,9285, 2738, 2288, 1233)1234567891011for (int i = 0; i

주어진 알고리즘을 직관적으로 생각하기 어렵다고 생각하여 문제를 4개의 작은 문제들로 분리해보았습니다. 먼저, 원본 문제의 링크입니다: https://algospot.com/judge/problem/read/ZIMBABWE 입력받은 양의 정수형 숫자 num에 대하여 각 자릿수의 숫자의 순서를 바꾸어 나타낼 수 있는 모든 경우의 수를 출력하라. 단, num의 각 자릿수의 숫자는 서로 다르다. (예: 123, 385, 9285, 2738은 가능하며, 2288, 1233은 불가능) 해설 : 먼저 int 형으로 입력받은 num의 각 자릿수의 숫자를 vector vec에 순차적으로 삽입합니다.12345678910111213141516171819#include #include #include using namespa..