0과 1의 쉼터

풀이 "백준 9251, LCS"에서 LCS를 출력하기위해 사용했던 j, i값을 이용해 문자열이 동일한 경우를 Recursion방식으로 찾았다. 소스코드 #include #define max(a, b) a > b ? a : b int dp[1001][1001]; char str[2][1001]; void LCS(int j, int i){ if (dp[j][i]) if (str[0][i-1] == str[1][j-1]){ LCS(j-1, i-1); printf("%c", str[0][i-1]); }else dp[j-1][i] > dp[j][i-1] ? LCS(j-1, i) : LCS(j, i-1); } int main(){ scanf("%s %s", &str[0], &str[1]); int i, j; for..

풀이 문자열의 길이가 폭발 문자열의 길이보다 크거나 같을 때, 폭발 문자열을 포함하고 있으면, 폭발 문자열의 길이만큼 index를 감소시키는 방식으로 출력할 문자열을 만들어주었다. 최종적인 index만큼 출력을 해줘도 되고, 마지막에 '\0'을 삽입해 문자열의 끝을 알려줘도 된다. 소스코드 #include #include char str[1000001], ans[1000001], explosion[37]; int main(){ scanf("%s %s", str, explosion); int len = strlen(str), exp_len = strlen(explosion), idx = 0; for (int i = 0; i = e..

풀이 첫째 줄에 입력받은 문자열의 각 문자와 둘째 줄에 입력받은 문자열간의 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[..

풀이 "백준 7677, Fibonacci"처럼, t개만큼 n번째 피보나치 수를 구하면 된다. 소스코드 #include #define ll long long const int MOD = 1e9; 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++) for (int j = 0; j < 2; j++) result[i][j] = temp[..

풀이 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..

풀이 T만큼 "백준 11778, 피보나치 수와 최대공약수"을 반복하는 문제이다. 소스코드 #include #define ll long long const int MOD = 1e9+7; ll X[2][2] = {0, 1, 1, 1}; ll gcd(ll a, ll b){ return b ? gcd(b, a%b) : a; } void fibo(ll result[][2], ll f[][2]){ int 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..

풀이 n번째 피보나치 수의 제곱의 합은 다음과 같은 규칙으로 구할 수 있다. "백준 11444, 피보나치 수 6" 코드를 사용해 풀이했다. 소스코드 #include #define ll long long const int MOD = 1e9 + 7; ll X[2][2] = {0, 1, 1, 1}; void fibo(ll result[][2], ll f[][2]){ int 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++) for (int j = 0; j..

풀이 짝수번째 피보나치 수에는 다음과 같은 규칙이 있다. "백준 11444, 피보나치 수 6" 코드를 사용해 풀이했다. 소스코드 #include #define ll long long const int MOD = 1e9 + 7; ll X[2][2] = {0, 1, 1, 1}; void fibo(ll result[][2], ll f[][2]){ int 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++) for (int j = 0; j < 2; j++) ..

풀이 홀수번째 피보나치 수에는 다음과 같은 규칙이 있다. "백준 11444, 피보나치 수 6" 코드를 사용해 풀이했다. 소스코드 #include #define ll long long const int MOD = 1e9 + 7; ll X[2][2] = {0, 1, 1, 1}; void fibo(ll result[][2], ll f[][2]){ int 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++) for (int j = 0; j < 2; j++) ..

풀이 n, m번째 피보나치 수의 최대공약수는, gcd(n, m)번째 피보나치 수와 같다. 구글에 영어로 검색하니 바로뜬다... 이 무슨 "백준 11444, 피보나치 수 6" 코드를 사용해 풀이했다. 소스코드 #include #define ll long long const int MOD = 1e9+7; ll X[2][2] = {0, 1, 1, 1}; ll gcd(ll a, ll b){ return b ? gcd(b, a%b) : a; } void fibo(ll result[][2], ll f[][2]){ int 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]..