본문 바로가기

분류 전체보기738

[백준 1799] 비숍 [C] 풀이 최악의 경우 모든 체스판의 정보가 1로만 이루어질 때, 시간초과가 발생하기 때문에, 효율적으로 풀이해야 한다. 모든 경우를 고려할 때 시간초과가 발생하는 이유 중 하나는 비숍이 규칙적으로 놓일 수 있는 공간에 대해 생각하지 않기 때문이다. 다음처럼 비숍을 놓는 경우를 생각해보자 즉, 흰색과 회색에 놓일 수 있는 비숍으로 구분해서 탐색한다면 규칙적으로 놓일 수 있는 공간대로 탐색할 수 있다. 입력받은 체스판의 정보에 대해 만약 놓을 수 없는 공간이라면 다음 공간으로 넘어가면 된다. 소스코드 #include #include bool board[11][11], l[19], r[19]; int N, result[2]; void bishop(int row, int col, int cnt, int color).. 2021. 9. 3.
[백준 14927] 전구 끄기 [C] 풀이 "백준 14939, 불 끄기"와 비슷하지만 행렬의 크기가 다른 문제다. 소스코드 #include #define min(a, b) a = 0 && ny >= 0 && nx < N && ny < N) temp[nx][ny] = (temp[nx][ny] == '1' ? '0' : '1'); } } int main(){ scanf("%d", &N); for (.. 2021. 9. 2.
[백준 14939] 불 끄기 [C] 풀이 주어진 예제는 직관적으로 풀이가 가능하지만 주어질 Test Case들을 고려하면 순차적으로 탐색하면서 풀이해야 한다. 우선 첫 번째 행에서 시도해볼 수 있는 모든 경우의 수를 시도한다면, 2~N번째 행에서는 이전 행의 불을 끄면 된다. N번째 행을 검사해서 불이 전부 다 꺼졌다면 입력된 예제가 모두 불이 꺼진 경우이므로 그때 누른 스위치의 개수들의 최솟값을 저장해 출력해주면 된다. 소스코드 #include #include #include #define min(a, b) a < b ? a : b char bulb[10][10], temp[10][10]; const char* lRow = "##########"; int dx[5] = {0, -1, 1}, dy[5] = {0, 0, 0, -1, 1}; .. 2021. 9. 2.
[백준 7579] 앱 [C] 풀이 입력받은 비용들의 총 합을 구해주고, 비용별로 확보할 수 있는 메모리의 최댓값을 구해야 한다. for (int i = 0; i = c[i]; cost--) dp[cost] = max(dp[cost], dp[cost-c[i]] + m[i]); 그 후 입력받은 M만큼의 메모리 이상을 확보하는 비용을 찾아 출력하면 된다. 소스코드 #include #define MAX 101 #define max(a, b) a > b ? a : b int c[MAX], m[MAX], dp[10001]; int main(){ int N, M; scanf("%d %d", &N, &M); for (int i = 0; i < N; i++) scanf("%d", &.. 2021. 9. 2.
[백준 2143] 두 배열의 합 [C] 풀이 A와 B의 부 배열에 대한 누적 합을 계산 후 정렬해주고, upper/lower bound로 가능한 경우를 계산해주면 된다. 단, 가능한 경우가 없을 수 있으니 left = diff) right = mid - 1; else left = mid + 1; mid = (left+right) / 2; }while (left 2021. 9. 2.
[백준 5347] LCM [C] 풀이 LCM을 구현하면 된다. 단, 결과가 너무 클 수 있으니 long long로 출력해주자. 소스코드 #include #define ll long long int gcd(int a, int b){ return b ? gcd(b, a%b) : a; } ll lcm(int a, int b){ return (ll)a*b/gcd(a, b); } int main(){ int n, a, b; scanf("%d", &n); while (n--){ scanf("%d %d", &a, &b); printf("%lld\n", lcm(a, b)); } } 출처 5347번: LCM 첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다.. 2021. 9. 2.

티스토리툴바