1. 텔레점프아이디어의 큰 틀은 생각보다 간단하다. 다만 이를 실제로 완성하는 건 꽤 까다로운 문제이다. * 먼저 처음에 A 에지 하나와 B 에지 모두를 소모해서, 앞 부분의 점을 다 연결 시켜준다. 1 - 2 / 1 - 3 / 2 - 4 / 3 - 5 ... * 이제 A 에지와 C 에지만이 남았다. B 에지로 만든 path의 두 끝 점 중 하나는 버리고 (즉 시작점으로 하고), 나머지 하나를 이어나갈 것인데, P / P + 3 / P + 6 ... 이런 식으로 이으면 중간에 공백이 생기니, A 에지를 하나 사용해서 P + 1 - P + 2를 이어주고, P + 1 / P + 4 ... 혹은 P + 2 / P + 5 ... 를 계속 이어준다. C 에지를 전부 소모할 때까지 이를 계속한다. * 남은 에지들은..
1. ČVENK점 (x, y)가 빈 공간이기 위해서는 x & y = 0이 성립해야 한다. 이 점에서는 항상 (0, 0)으로 가는 경로가 존재하는데, 다음과 같은 방법으로 이를 찾을 수 있다. * x == 0 || y == 0일 경우에는 자명하게 경로를 찾을 수 있다. * x와 y가 모두 0이 아니라고 가정하자. lowest significant bit (LSB) 가 작은 쪽을 찾자. 여기서는 일반성을 잃지 않고 x라고 한다. 그렇다면, (x - LSB(x), y) - (x, y) 를 잇는 경로는 비어 있다. (x - LSB(x), y) 에서 재귀적으로 계속 경로를 찾아나간다.이 경로는 항상 존재하며 유일하다. 이는 빈 공간들이 트리를 이룬다는 증명이 되기도 한다. (사실 그건 사진을 보면 쉽게 눈치챌 수..
1. 숫자카드간단한 동적 계획법이다. 문자열을 길이 1 / 길이 2의 문자열로 분해하는 경우의 수를 세는 것인데, dp[i] = 앞 i자리 문자를 모두 분해하는 경우의 수라고 하면, dp[i-1]과 dp[i-2]에 대한 점화식이 나오고, 이를 통해 해결할 수 있다. 2. 놀이공원배열을 통해서 각 1분 단위의 시간에 휴식이 가능한지를 관리한다. 놀이기구 하나에 대해서, (시작 시간 - 10분) ~ (종료 시간 + 10분) 동안은 휴식이 불가능하다. 고로 각 놀이기구 마다 이 구간에 체크해 두면, 해당 단위 시간에 휴식이 가능한 지 알 수 있다. 이 정보를 안다면, 이 정보를 안다면, 가장 긴 휴식 가능 구간을 구하는 문제는, 0과 1로 이루어진 배열에서, 가장 긴 0으로 이루어진 연속 구간을 구하는 문제가..
- Total
- Today
- Yesterday