[백준 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.
[백준 1788] 피보나치 수의 확장 [C]
풀이 F(1) = 1 = F(0) + F(-1), F(-1) = 1 F(0) = 0 = F(-1) + F(-2), F(-2) = -1 F(-1) = 1 = F(-2) + F(-3), F(-3) = 2 F(-2) = -1 = F(-3) + F(-4), F(-4) = -3 F(-3) = 2 = F(-4) + F(-5), F(-5) = 5 n이 음수이고, 짝수일때만, F(n)이 -1이다. 소스코드 #include int main(){ int n, op = 1; long long dp[2] = {0, 1}; scanf("%d", &n); if (n = 2){ for (int i = 1; i..
2021. 8. 10.
