0과 1의 쉼터

풀이 벡터곱을 이용해 P1P2에서 P3의 방향을 구할 수 있다. 소스코드 #include typedef struct{ int x, y; }Point; int main(){ Point p[3]; for (int i = 0; i 0 ? '1' : '0'); } 출처 및 참고자료 11758번: CCW 첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 ..

풀이 16까지 1의 분포는 다음과 같다. N N의 2진수 1의 개수 1 1 1 2 1 0 2 3 1 1 4 4 1 0 0 5 5 1 0 1 7 6 1 1 0 9 7 1 1 1 12 8 1 0 0 0 13 9 1 0 0 1 15 10 1 0 1 0 17 11 1 0 1 1 20 12 1 1 0 0 22 13 1 1 0 1 25 14 1 1 1 0 28 15 1 1 1 1 32 16 1 0 0 0 0 33 2^x 자리 수는 2^(x+1)마다 반복된다는 것을 알 수 있다. 때문에, (N+1)을 2^(x+1)로 나눈 몫을 2^x만큼 곱하면 완전히 반복되는 구간에 존재하는 1의 개수를 구할 수 있다. 완전히 반복되지 않은 구간에서의 1의 개수는, 2^x 자리 수가 1인경우 (N+1)을 2^x로 나눈 나머지의 개수..

풀이 "백준 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[..

풀이 "백준 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..

풀이 "백준 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..