0과 1의 쉼터

풀이 건물 W를 완성하기 위해서는 건물 1에서 건물 W로 향하는 건물들이 완성되어야 하기 때문에, W값에서 역으로 DFS방식을 사용했다. W에서 1로 향하는 건물들이 모두 건설되어야 하기 때문에 D값이 가장 큰 값을 time에 넣어주어 반환해야 한다. 좀더 효율적인 탐색을 위해 총 time을 check에 넣는 memoization방식으로 해결했다. 단, D값은 0이상이기 때문에 -1로 초기화해서 사용해야 한다. 소스코드 #include #include #include #define max(a, b) a > b ? a : b int D[1001], N, check[1001]; bool O[1001][1001]; int construction(int c){ if (check[c] != -1) return c..

풀이 스도쿠를 완성시키고, 81자리의 수가 제일 작은 경우를 출력하면 되는 문제이다. Backtracking방식으로 스도쿠에 넣어줄 수 있는 작은 수 부터 탐색하면서, 만약 81번째 자리에 도달했다면 가장 작은 81자리의 수를 완성시킨 것이기 때문에 출력을 해주고 중단을 해줘야한다. 소스코드 #include int arr[9][9], print = 1; int check(int x, int y, int val){ for (int i = 0; i < 9; i++) if (arr[x][i] == val || arr[i][y] == val) return 0; x = (x/3)*3; y = (y/3)*3; for (int i = x; i < x+3; i++) for (int j = y; j < y+3; j++)..

풀이 연속된 수들의 부분합이기 때문에 Two Pointers로 쉽게 구현할 수 있다. start, end가 가르키는 배열의 합들이 S이상이면 최소 길이를 구해야 하며, 만약 sum이 S보다 작으면 end+1번째 요소를 더해주고, 그렇지 않다면 start번째 요소를 빼주는 방식으로 풀이했다. 소스코드 #include #define min(a, b) a < b ? a : b int main(){ int arr[100000], N, S, start = 0, end = 0; scanf("%d %d %d", &N, &S, &arr[0]); for (int i = 1; i < N; i++) scanf("%d", &arr[i]); int cnt = 1e5, sum = arr[0]; while (start = S) c..

풀이 "백준 11758, CCW"를 이용해 풀이했다. 벡터곱의 값은 두 벡터로 이루어지는 평행사변형의 넓이와 동일하므로, 벡터곱의 값을 반으로 나눈 값을 더해주면 된다. 기준점이 필요하기 때문에 처음에 입력받은 좌표를 기준점으로 했다. 소스코드 #include typedef struct{ double x, y; }Point; int main(){ int N; scanf("%d", &N); Point p[N]; for (int i = 0; i < N; i++) scanf("%lf %lf", &p[i].x, &p[i].y); double sum = 0; for (int i = 1; i < N; i++) sum += ((p[i-1].x - p[0].x)*(p[i].y - p[0].y) - (p[i-1].y -..

풀이 벡터곱을 이용해 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..