본문 바로가기

골드90

[백준 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.
[백준 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.
[백준 7453] 합이 0인 네 정수 [C] 풀이 제한시간이 12초이기 때문에 모든 쌍을 확인하면 시간초과가 발생한다. 때문에, A~B, C~D의 합을 저장하고, Binary Search을 사용해 풀이했다. 합이 0인 쌍의 개수를 모두 구해야 하므로, 다음과 같이 upper/lower bound를 구현했다. qsort(AB, N, sizeof(int), compare); qsort(CD, N, sizeof(int), compare); long long cnt = 0; for (int i = 0; i 0) right = mid; else left = mid .. 2021. 8. 16.
[백준 1937] 욕심쟁이 판다 [C] 풀이 시간 제한이 있어 dfs로 이미 탐색한 영역에는 이동할 수 있는 칸의 수의 최댓값을 dp에 기록하는 방식으로 풀이했다. 소스코드 #include #define max(a,b) a > b ? a : b #define MAX 500 int forest[MAX][MAX], n; int dp[MAX][MAX]; int dx[4] = {-1, 1}, dy[4] = {0, 0, -1, 1}; int dfs(int x, int y){ if (!dp[x][y]){ dp[x][y] = 1; for (int i = 0; i = 0 && ty >= 0 && tx < n && ty < n) if (forest[tx][ty].. 2021. 8. 16.

티스토리툴바