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

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

풀이 다음과 같이 행렬을 이용해 피보나치 수를 구할 수 있다. "백준 10830, 행렬 제곱" 코드를 이용해 완성했다. 소스코드 #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++) ..

풀이 시간 제한이 있어 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]..

풀이 연속된 소수의 합이므로, 소수로만 이루어진 배열에서 투 포인트를 적용하면 된다. 에라토스테네스의 체로 소수가 아닌 것들을 구분하여 소수로만 이루어진 배열을 만들고, 투 포인트 방식으로 풀이했다. 소스코드 #include #include #include #define MAX 4000001 bool not_prime[MAX]; int sum_prime[MAX/10]; int main(){ int N; scanf("%d", &N); int sq = sqrt(N); for (int i = 2; i

풀이 i * j로 구성된 N x N크기의 배열의 수들을 작은 오름차순으로 나열했을 때, K번째 수가 무엇인지 알아내는 문제다. N = 3, K = 7일 때, K번째 수는 다음과 같다. K 1 2 3 4 5 6 7 i*j 1 2 2 3 4 4 6 즉 임의의 수 mid에 대해 i*j

풀이 Dynamic Programming의 Memorization 방식으로 풀이했다. (S~E) 구간이 팰린드롬인지 알기 위해서는 (S+1 ~ E-1), (S+2 ~ E-2), ... (X, X+1) or (X, X)구간의 수들이 팰린드롬인지 알아내는 과정을 반복해야한다. 길이가 3이상일 때, 요소가 홀수개인 팰린드롬은 최종적으로 길이가 1인 팰린드롬의 여부에 따라, 요소가 짝수개인 팰린드롬은 최종적으로 길이가 2인 팰린드롬의 여부에 따라 결정되기 때문에 다음과 같이 나누었다. 입력을 받을 때 길이가 1, 2인 펠림드롬을 확인하고, for (int i = 1; i 1 && arr[i] == arr[i-1]) dp[i-1][i] = 1; } 입력이 끝난 후 길이가 3 이상인 팰린드롬을 구했다. for (i..