문제양수 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; }
전형적인 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
문제 a. 문제 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다. 이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을..
