[백준 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.
[백준 1915] 가장 큰 정사각형 [C]
풀이 dp[i][j]를 기준으로, dp[i][j-1], dp[i-1][j-1], dp[i-1][j]가 모두 0이 아닌 정수일 때, 이들의 최솟값에 1을 더한 값이 dp[i][j]를 기준으로 만들어지는 정사각형의 한 변의 길이이다. 가장 큰 dp[i][j]값을 max에 담아, max의 제곱을 출력해주면 된다. 소스코드 #include int dp[1001][1001]; int min(int a, int b, int c){ if (a < b && a < c) return a; return b < c ? b : c; } int main(){ int n, m; scanf("%d %d", &n, &m); for (int i = 1; i
2021. 8. 16.
[백준 15988] 1, 2, 3 더하기 3 [C]
풀이 "백준 9095, 1, 2, 3 더하기"의 확장 문제이다. 1e6 까지 미리 구해놓자. 소스코드 #include const int MOD = 1e9+9; int dp[1000001] = {1, 2, 4}; int main(){ for (int i = 3; i < 1000001; i++) dp[i] = ((dp[i-1]+dp[i-2])%MOD +dp[i-3]) %MOD; int N, T; for (scanf("%d", &T); T--;){ scanf("%d", &N); printf("%d\n", dp[N-1]); } } 출처 및 참고자료 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. ..
2021. 8. 16.
