본문 바로가기
728x90
반응형

algorithm56

[algorithm] 백준 - 조합 0의 개수 우선 곱셈으로 0을 어떻게 만들 수 있을까? 2와 5가 곱해졌을 때 10으로 0의 개수가 1이다. 4와 25가 곱해졌을 때 100으로 0의 개수가 2이다. 즉 2와 5는 0을 만드는 구성원이라는 것을 알 수 있다. 그렇다면 2가 1개 5가 1개일 때 0 1개를 만들 수 있다. 2가 2개 3개더라도 5는 1개이면 0은 언제나 1개이다. 즉 2와 5의 개수 중 가장 작은 수가 0의 개수이다. 조합은 라는 식을 갖는다. 그렇다면 n!에서의 2의 개수 - k! 에서의 2의 개수 - (n-k)! 에서의 2의 개수와 n!에서의 5의 개수 - k! 에서의 5의 개수 - (n-k)! 에서의 5의 개수 중 가장 작은 수는 0의 개수라는 것을 알 수 있다. cout 2020. 11. 4.
[algorithm] 백준 - 리모컨 brute force 문제이다. 가능한 모든 리모컨 채널을 돌리면서 최소 몇번 눌러지는 지를 체크하면 된다. 1. 모든 가능성을 열어두기 위해 중복순열로 자릿수는 0부터 6까지 모든 경우를 구했다. 만약 테스트 케이스가 10 2 1 0 이런 경우 자릿수가 1인 9로 이동하는 채널 수가 적기 때문이다. 따라서 모든 자릿수에 대한 채널을 구해야한다. 그리고 이동하려하는 리모컨 채널 - 만들어진 리모컨 + 리모컨을 누른 값 중 가장 작은 값을 구한다. 2. 현재 채널인 100에서 이동하고자 하는 리모컨 채널을 뺀 값과 위에서 구한 값을 비교해서 가장 작은 값을 출력한다. 코드는 이렇다. #include #include #include using namespace std; unsigned long answer .. 2020. 11. 4.
[algorithm] 백준 - 수 이어 쓰기 1 brute force문제이다. 입력 수가 1억이하이고, 시간 제한이 1초이므로 실제로 이 수를 이어서 써서 자릿수를 구하게 되면 시간초과가 날 것이다. 입력수의 길이를 구하고 길이 -1 까지의 자릿수를 모두 더한 후, (입력수 - 10 ^ (length - 1) + 1) * length와 값을 더했다. 만일 120이라고 가정했을 때, 120의 길이는 3이다. 3 - 1 = 2의 자릿수를 모두 더한다. 9 - 1 + 1 + (99 - 10 + 1) * 2 (120 - 100 + 1)* 3 을 더하면 252이다. //수 이어쓰기 1 #include #include using namespace std; int getNumCount(int tenNum, int nineNum){ return nineNum - t.. 2020. 11. 3.
[algorithm] 백준 - 가장 긴 바이토닉 부분 수열 이 문제는 DP로 가장 긴 증가하는 부분 수열과 관련된 문제이다. daewoony.tistory.com/44 [algorithm] 백준 - 가장 긴 증가하는 부분 수열 1 & 4 DP 문제이다. 순서대로 반복문을 돌다가 증가하는 부분을 확인하면서 값을 올리는 방식으로 풀면 된다. // 가장 긴 증가하는 부분수열 4 #include #include using namespace std; int main(void){ int count, ans.. daewoony.tistory.com 증가하다가 감소하는 수열, 증가하는 수열, 감소하는 수열 모두 바이토닉 수열에 해당된다. 순서대로 반복문을 돌다가 현 위치의 수 부터 이전 수를 비교했을 때 현 위치의 수가 큰 수일 경우 값을 올리는 방식으로 가장 긴 증가하는 수.. 2020. 11. 3.
[algorithm] 백준 - 합분해 이 문제는 DP문제이다. 0부터 n까지 k개를 더해서 n이 되는 경우의 수를 구하는 것이며, 덧셈의 순서가 바뀐 경우는 다른 경우로 센다. 그리고 한개의 수를 여러번 쓸 수 있다. n은 2고 k는 2이라고 예를 들어보자. k n n을 구하기 위한 과정 1 0 0 경우의 수 : 1개 1 1 1 경우의 수 : 1개 1 2 2 경우의 수 : 1개 2 0 0 0 경우의 수 : 1개 2 1 0 1 1 0 경우의 수 : 2개 2 2 0 2 1 1 2 0 경우의 수 : 3개 따라서 3개라는 것을 알 수 있다. 여기서 알아야할 것은 n을 구하기 위해서는 사실 k n n을 구하기 위한 과정 1 0 0 경우의 수 : 1개 1 1 1 경우의 수 : 1개 1 2 2 경우의 수 : 1개 2 0 0 0 경우의 수 : 1개 2 1.. 2020. 11. 3.
[algorithm] 백준 - 제곱수의 합 DP문제이다. 어떤 자연수는 제곱수의 합으로 이루어져 있으며, 합을 이루는 가장 적은 항의 개수를 리턴하는 것이다. 자연수 제곱수의 합 1 1 18 (3개) 4^2 + 2 = 18 (2개) 3^2 + 3^2 = 18 ... 가장 적은 개수: 2개 제곱 수가 가장 큰 수와 상관 없이 적은 개수를 이루기 위해서는 모든 제곱수와 비교해서 적은 개수를 구해야한다. 따라서 제곱수에 해당하는 수는 제곱수 1개로 이루어져 가장 적은 수이므로 별도로 vector에 삽입하고, if((int)sqrt(i) == sqrt(i)){ dp[i] = 1; multiplyVector.push_back(i); } 제곱수가 아닌 수는 삽입된 수 중 가장 적은 항으로 이룰 수 있는 경우를 찾아 DP에 삽입했다. dp[i] = 98765.. 2020. 11. 3.
728x90
반응형

티스토리툴바