본문 바로가기

분류 전체보기723

[백준 10830] 행렬 제곱 [C] 풀이 분할 정복을 이용한 거듭제곱 알고리즘으로 행렬의 제곱을 구현해주어야 시간 초과가 발생하지 않는다. 소스코드 #include int N; void square(int result[][5], int matrix[][5]){ int temp[5][5] = {0,}; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) temp[i][j] += (result[i][k]*matrix[k][j]) %1000; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) result[i][j] = temp[i][j] %1000; } int main(){ long long B; .. 2021. 8. 21.
[백준 13172] Σ [C] 풀이 지문이 어마무시하게 길면서 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 .. 2021. 8. 20.
[백준 16953] A → B [C/C++] 풀이 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 .. 2021. 8. 20.
[백준 5639] 이진 검색 트리 [C] 풀이 조건에 맞게 값을 넣어줄 수 있는 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.. 2021. 8. 19.
[백준 2879] 코딩은 예쁘게 [C] 풀이 현재 탭의 개수에서 올바른 탭의 개수만큼 빼서 계산할 탭의 수만 남겨준 후, 부호가 같은 그룹을 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,.. 2021. 8. 19.
[백준 1082] 방 번호 [C] 풀이 가장 큰 방 번호는 만들어 질 수 있는 가장 긴 방 번호와 작거나 같다.. 따라서, 가격이 가장 저렴한 방 번호로 가장 긴 번호를 만들고, 번호의 앞자리 부터 남은 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.. 2021. 8. 19.

티스토리툴바