0과 1의 쉼터

풀이 지문이 어마무시하게 길면서 Fermat’s little theorem에 대해 설명이 친절한 문제이다. 요점은 다음과 같다. M개의 N과 S에 대해 S*N^(MOD-2)의 합들을 MOD로 나눈 나머지를 구하면 된다. 단, N^(MOD-2)를 구하는 과정에서 수가 너무 커지므로 중간과정마다 MOD로 나누어줘야 한다. 소스코드 #include const int MOD = 1e9+7; int main(){ long long sum = 0, N; int M, S; scanf("%d", &M); while (M--){ scanf("%d %d", &N, &S); long long temp = 1, k = MOD-2; while (k){ if (k & 1) temp = temp*N %MOD; k >>= 1; N ..

풀이 Queue에 연산값과 최솟값을 저장해주어, 연산값이 B가 될 때까지 탐색해주는 방식으로 풀이했다. 처음으로 들어오는 값이 1e8일 경우 10을 곱해주면 int의 범위를 벗어나므로 num은 long long으로 담아주었다. 만약 연산이 불가능하다면, num == B 조건을 만족하지 못하고 모든 Queue가 비었다는 것이므로, -1을 출력하면 된다. 소스코드 #include #include using namespace std; void bfs(int A, int B){ queue q; q.push(make_pair(A, 1)); while (!q.empty()){ long long num = q.front().first; int cnt = q.front().second; q.pop(); if (num ..

풀이 조건에 맞게 값을 넣어줄 수 있는 Binary Search Tree를 구현하는 문제이다. 소스코드 #include #include typedef struct node{ int data; struct node *left, *right; }*pNode; void postorder(pNode root){ if (root == NULL) return; postorder(root->left); postorder(root->right); printf("%d\n", root->data); } pNode make_tree(pNode root, int data){ if (root == NULL){ root = (pNode)malloc(sizeof(pNode)); root->data = data; root->left..

풀이 현재 탭의 개수에서 올바른 탭의 개수만큼 빼서 계산할 탭의 수만 남겨준 후, 부호가 같은 그룹을 start, end로 index 범위로 지정해주고, 그룹에서 뺄 수 있는 탭의 최솟값만큼 한 번에 빼는 방식으로 풀이했다. 소스코드 #include #include int main(){ int N; scanf("%d", &N); int dp[N], val, line = N; for (int i = 0; i < N; i++) scanf("%d", &dp[i]); for (int i = 0; i < N; i++){ scanf("%d", &val); dp[i] -= val; !dp[i] && --line; } int cnt = 0; while (line){ int start = 0, end, min = 80,..

풀이 가장 큰 방 번호는 만들어 질 수 있는 가장 긴 방 번호와 작거나 같다.. 따라서, 가격이 가장 저렴한 방 번호로 가장 긴 번호를 만들고, 번호의 앞자리 부터 남은 M을 이용해 가능한 큰 수로 바꾸어 주면된다. 단, 앞자리에 0이 올 수 있는 경우는 방 번호가 0인 경우만 가능하므로 M이 작아 9~1의 번호로 교체가 불가능해 여전히 0이라면, 교체가 가능할 때까지 min만큼 다시 M에 더해주어야 한다. 소스코드 #include int main(){ int N, M; scanf("%d", &N); int price[N], min = 50, idx; for (int i = 0; i = price[i]){ min = price..

풀이 오일러의 정리를 이용해서 풀이하는 문제다. 이나... 자료가 너무 부족하다. 오일러의 정리에 대해 자료를 찾던 도중 다음과 같은 자료를 찾았다. a와 n이 서로소이면, a^m ≡ 1 mod n에서 m = EPF(n)을 만족하는 정수 m이 적어도 하나 존재한다. a (mod n)에 대한 차수가 위 식의 m이 될 수 있다. (N ^ f( N, EPF(M) ) ) % M을 재귀호출해 찍었다. 풀이했다. 입력받거나 전달받은 N과 M 둘 중 하나가 1일 때, 1을 반환해주면 위 식의 계산에 따라 원하는 결과를 얻을 수 있다. 단, 제곱을 구하는 과정에서 long long으로도 담을 수 없는 수가 나온다. (N^(N^N)) mod M != (N^((N^N) mod M)) mod M 이므로, M이 아닌 EPF(..

풀이 "백준 15664, N과 M (10)"에서 기존에 i번째 요소를 사용했는지를 확인하기 위해 사용한 check를 빼면 해결할 수 있다. 소스코드 #include #include int N, M, arr[8], visited[8]; int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } void BT(int depth, int start){ for (int i = start, temp = 0; i < N; i++) if (temp != arr[i]){ temp = visited[depth] = arr[i]; if (depth + 1 == M){ for (int idx = 0; idx < M; idx++) printf("%d ",..

풀이 "백준 15663, N과 M (9)"에서 기존에 i번째 요소를 사용했는지를 확인하기 위해 사용한 check를 빼면 해결할 수 있다. 소스코드 #include #include int N, M, arr[7], visited[7]; int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } void BT(int depth){ for (int i = 0, temp = 0; i < N; i++) if (temp != arr[i]){ temp = visited[depth] = arr[i]; if (depth + 1 == M){ for (int idx = 0; idx < M; idx++) printf("%d ", visited[idx]); ..

풀이 "백준 15651, N과 M (3)"와 비슷하다. 1부터 N까지가 아닌 입력받은 수에 대해 모든 조합 가능한 수를 출력하면 된다. 소스코드 #include #include int N, M, visited[7], arr[7]; int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } void BT(int depth){ for (int i = 0; i < N; i++){ visited[depth] = arr[i]; if(depth + 1 == M){ for (int idx = 0; idx < M; idx++) printf("%d ", visited[idx]); putchar(10); }else BT(depth + 1); } } i..

풀이 "백준 15664, N과 M (10)"에서 사용한 코드로 해결이 된다. 소스코드 #include #include #include bool check[8]; int N, M, arr[8], visited[8]; int compare(const void *a, const void *b){ return *(int*)a - *(int*)b; } void BT(int depth, int start){ for (int i = start, temp = 0; i < N; i++) if (!check[i] && temp != arr[i]){ temp = visited[depth] = arr[i]; check[i] = true; if (depth + 1 == M){ for (int idx = 0; idx < M; i..