본문 바로가기

다이나믹 프로그래밍32

[백준 9251] LCS [C] 풀이 첫째 줄에 입력받은 문자열의 각 문자와 둘째 줄에 입력받은 문자열간의 LCS를 구하는 방식으로 풀이했다. (j, i)번째에 각 문자열의 문자가 동일하다면, (j-1, i-1)번째의 LCS보다 1만큼 길다. 만약 문자가 같지않다면, 이전 LCS의 값 중 큰 값과 일치한다. 소스코드 #include #define max(a, b) a > b ? a : b int dp[1001][1001]; int main(){ char str[2][1001]; scanf("%s %s", &str[0], &str[1]); int i, j; for (i = 0; str[0][i]; i++) for (j = 0; str[1][j]; j++) if (str[0][i] == str[1][j]) dp[j+1][i+1] = dp[.. 2021. 8. 24.
[백준 15624] 피보나치 수 7 [C] 풀이 "백준 2747, 피보나치 수"를 풀었던 방법으로 해결할 수 있다. 소스코드 #include const int MOD = 1e9 + 7; long long fibo(int n){ long long fiboNum[2] = {0, 1}; for (int i = 1 ; i < n; i++) fiboNum[(i+1)%2] = (fiboNum[i%2] + fiboNum[(i-1)%2]) %MOD; return fiboNum[n%2]; } int main(){ int n; scanf("%d", &n); printf("%lld", fibo(n)); } 출처 및 참고자료 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net.. 2021. 8. 24.
[백준 7677] Fibonacci [C] 풀이 n이 -1일 때까지 n번째 피보나치 수를 출력해주면 된다. "백준 11444, 피보나치 수 6" 코드를 사용해 풀이했다. 10,000으로 나눈 나머지로 계산해 출력하면 된다. 소스코드 #include #define ll long long #define MOD 10000 ll X[2][2] = {0, 1, 1, 1}; void fibo(ll result[][2], ll f[][2]){ ll temp[2][2] = {0,}; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) temp[i][j] += (result[i][k]*f[k][j]) %MOD; for (int i = 0; i < 2; i++) fo.. 2021. 8. 23.
[백준 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.
[백준 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.