문제양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.입력첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.출력첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.예제 입력 124 2예제 출력 18예제 입력 212예제 출력 24예제 입력 363 4 2 12 6 8예제 출력 324예제 입력 41414 26456 2 28 13228 3307 7 23149 8 6614 46298 56 4 92596예제..
문제2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 각 자릿수가 모두 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.입력입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.출력각 자릿수가 모두 1로만 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다예제 입력 13612예제 출력 1379901풀이 1, 11, 111...으로 한 자리씩 늘려가며 입력받은 수의 배수인지 확인한다.아래 버튼를 눌러 풀이를 확인하세요더보기#include using namespace std;int main() { int n; while (cin >> n) { long long remainder = 1 % n; int c..
LIS와 유사한 문제, 다양한 방법으로 해결할 수 있다. #include #include #include using namespace std; int a[100001], exist[1000001], N; int binary_search(int start, int end, int element) { while (start a[mid]) start = mid + 1; else end = mid; } if(a[end]==element) return end; else return -1; } int main(void) { cin >> N; for(int i=0; i> a[i]; sort(a, a+N); for(int i=..
zeros배열과 ones 배열을 활용하여 각 숫자에서 0과 1이 나온 횟수를 메모이제이션으로 저장한다. #include #include using namespace std; int zeros[41], ones[41]; int z(int n) { if(zeros[n]) return zeros[n]; else if(n==0) return zeros[n]=1; else if(n==1) return zeros[n]=0; else return zeros[n]=z(n-1)+z(n-2); } int o(int n) { if(ones[n]) return ones[n]; else if(n==0) return ones[n]=0; else if(n==1) return ones[n]=1; else return ones[n]=..
LIS 알고리즘을 사용하면 간단하게 해결할 수 있다. #include using namespace std; int a[1000], length[1000], n; void dpFunc() { int res=0; for(int i=0; ires) res=length[i]; } cout > n; for(int i=0; i> a[i]; dpFunc(); return 0; }
🧐 최장 증가 부분 수열 (LIS)란? 최장 증가 부분 수열, Longest Increasing Subseqeunce는 어떠한 수열의 부분 수열중 오름차순으로 증가하는 가장 긴 수열을 의미한다. (이때 각 원소는 연속할 필요는 없다.) 아래의 예시 수열을 보자. [ 7, 3, 5, 2, 7, 4, 8, 2] 이 수열에서 증가하는 순열에는 [2, 4], [2, 4, 8], [3, 5] 등 다양한 것이 있지만 LIS는 [3, 5, 7, 8]이 된다. 📝 LIS를 구해보자 LIS를 구하는 방법에는 동적 계획법(DP)와 이분탐색으로 크게 두가지의 방법이 있다. DP는 $O(n^2)$의 시간복잡도를 보이며, 이분탐색으로 구현하게 되면 $O(n\log{n})$의 시간복잡도가 나타난다. 1) 동적 계획법 (Dynam..
전형적인 DP 문제로, 점화식만 이끌어 낸다면 쉽게 풀 수 있다.n번째에서의 경우의 수를 계산한다 하자n-1에서 n으로 가는 경우의 수는 한가지다.n-2에서 n으로 가는 경우는 n-2+1+1, n-2+2로 2가지다. 이때 n-2+1+1은 n-1에서 n으로 갈 떄 세준 케이스 이므로 n-2+2 의 한가지 경우만 센다.마찬가지로 n-3에서 n으로 가는 경우의 수도 한가지이다.즉, 다음과 같이 식을 세울 수 있다. DP[n]=func(n-1)+func(n-2)+func(n-3) 스스로 코드를 짠 후 아래를 눌러 읽어보자.더보기#include using namespace std;int DP[11];int func(int n) { if(DP[n]) return DP[n]; if(n==1) return ..
DP를 사용하여 가능한 최수 경우의 수를 Bottom-Up 방식으로 구해준다.#include using namespace std;int main() { int N, DP[1000001]; cin >> N; DP[1]=0; for(int i=2; i
문제 a. 문제 양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다. 무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다. 구슬이 3g인 경우 아래 과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다. 와 같은 방법을 사용하면 구슬이 5g인지도 확인할 수 있다. 구슬이 2g이면 주어진 추를 가지고는 확인할 수 없다. 추들의 무게와 확인할 구슬들의 ..
7576번 토마토 문제에 세로축만 추가된 것으로 마찬가지로 BFS를 사용하면 된다. 풀이는 이전 글을 참고하자. #include #include #include using namespace std; int M, N, H, a[100][100][100]={}; queue q; int dh[6]={-1, 1, 0, 0, 0, 0}; int dn[6]={0, 0, -1, 1, 0, 0}; int dm[6]={0, 0, 0, 0, -1, 1}; bool isDone() { for(int i=0; i H; for(int i=0; i
