케이스윔의 개발 블로그

문제1부터 N까지 마을이 있을 때 마을을 순회할 수 있는 최소비용을 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/2098) 풀이이 문제는 Bitmask를 사용해서 dp를 만들어 나가보려고 푼 문제입니다. 여기서는 모든 마을을 순회해야할 때 방문한 마을을 표시하기 위해 Bitmask를 사용해보았습니다. dp를 통해 문제를 풀기 위해 배열이 필요하고, Bitmask를 사용한다면 어느 마을을 방문했는지 알 수 있으므로 dp배열에서 바로 사용을 할 수 있게 됩니다. 1번 마을을 방문했다면 1이고, 2번 마을을 방문했다면 10, 3번 마을을 방문했다면 100, 세 마을을 전부 방문했다면 111로 표현할 수 있습니다. 이 때 특정한 i번째의 마을을 방문했는지 알려면..

문제N, L, R이 주어진다. N개의 건물을 왼쪽에서 보았을 때는 L개가 보이고 오른쪽에서 보았을 때 R개가 보이는 경우의 수를 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/1328) 풀이처음에 보자마자 너무 어렵다고 생각이 들었습니다! 그리고 아주 이상한 방법으로 많이 접근을 했습니다. 다이나믹 프로그래밍 카테고리에서 골랐기 때문에 dp로 풀어야겠다는 생각은 들었지만 점화식을 세울 수 없었습니다. 처음엔 1~N까지의 건물이 주어질 때 높이가 N인 건물을 고정시키면 왼쪽, 오른쪽으로 경우의 수를 쪼갤 수 있어서 그 방법을 통해서 시도해보려 했지만 너무 어렵고 무식한 방법이었습니다. 결국 다른 분들이 풀이한 것들을 보고 힌트를 얻어서 풀었습니다. N-1개의..

문제각 배열의 원소가 주어지고, i, j, x, y가 주어질 때 (i, j)칸에서 (x, y)칸까지의 합을 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/2167) 풀이처음에는 단순히 일렬로 놓여있는 배열이라 생각하고 (i, j)칸에서부터 (x, y)칸까지의 합을 구하는 줄 알았는데 그게 아니라 사각형을 그린다고 했을 때 왼쪽 위의 점이 (i, j)이고 오른쪽 아래점이 (x, y)인 것이었습니다. 어떻게하면 숫자가 크지 않다면 2중 for문을 통해서 구할 수도 있겠지만 합을 구해야하는 경우의 수가 최대 10000개가 될 수 있기 때문에 dp를 이용해야했습니다. 처음엔 전.혀 감이오지 않아서 넘겨버렸던 문제였는데 그림을 그려서 생각해보니 쉽게 생각할 수 있었..

문제로봇이 동서남북 4개의 방향 중에 하나를 선택해서 이동하는데 N번의 행동을 취한다. 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. 각 방향으로 이동할 확률이 주어질 때 로봇의 이동 경로가 단순할 확률을 구하는 프로그램을 작성하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/1405) 풀이같은 곳을 한 번보다 많이 이동하지 않는 이동경로 = visited 배열이 0인 곳만 방문하는 경우를 의미합니다. N은 14보다 작거나 같으므로 visited 배열을 만들기 위한 값을 생각해보면 동, 서, 남, 북쪽으로만 N번 이동할 수 있으므로 (2*N)*(2*N)의 크기가 필요합니다. 출발점은 N, N이라고 생각할 수 있습니다. 그 다..

문제개수 N이 주어지고 가능한 모든 N*(N+1)/2개의 구간의 합에 대한 부호가 주어질 때, 수열 N을 구하시오.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1248) 풀이처음에 어렵다고 느껴서 헤맸던 문제입니다! N이라는 숫자가 주어지고 구간의 합의 모든 조합에 대한 +, -, 0가 주어질 때 이 모든 조건을 만족하는 수열을 구해야합니다. 처음에는 입력을 1차원 배열로 받다보니 i번째 자신에 대한 부호를 찾는 것도 몇번째에 위치하고 있는지 계산을 해야해서 복잡해졌습니다. 그래서 이 방법을 처음에 시도했다가 배열을 N*N으로 만들어서 첫째 줄에서는 N개를 사용, 두번째 줄에는 N-1개를 사용하도록 했습니다. 그렇게 하니 i번째 자리의 부호를 알기 위해서는 nu..

문제2차원 배열로 빙산이 주어졌을 때, 1년이 지날 때마다 0인 바닷물과 인접한 만큼 빙산의 높이가 줄어든다. 한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/2573) 풀이정답율이 낮은 문제여서 어려울 줄 알았는데 빙산을 녹이는 부분, BFS(또는 DFS)를 통해서 빙산의 덩어리가 두덩어리로 나누어질 때를 확인해주면 되는 문제입니다. 처음엔 이중 for문을 통해서 각 칸에서 빙산이라면 얼마나 녹아야하는지를 탐색하려했는데 빙산이 아닌 부분(0인 곳)이 많을 경우에는 시간이 많이 걸릴 것 같아서 처음 입력을 받을 때 queue를 통해서 따로 빙산을 저장해줬습니다. 그 다..

문제n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1912) 풀이처음에는 문제를 보고 난해하다 생각했습니다.(*^^*) 일부 연속된 수를 합해서 최대의 수를 만들어야했는데 음수가 과연 포함될 수 있을지에 대한 고민이 들었습니다. 그냥 생각해보면 음수가 더해지면 작아지니까 아닐 것 같았는데 생각해보니 100 -1 100 이라는 경우..

문제0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/2225) 풀이문제를 읽어보았을 때 꽤 간단한 문제라고 느껴서 바로 점화식을 세웠지만 조건을 하나 놓쳐서 다시 읽어본 문제입니다. 식은 간단히 세울 수 있었습니다 dp[N][K]를 K개의 정수를 더해서 N을 만드는 것이라고 정의를 합니다. 그렇게 되면 dp[N][K] = dp[N-(N또는 보다 작은 정수)][K-1]의 합이 됩니다. 즉 N또는 N보다 작은 숫자를 K-1개로 만들었다면 거기에다가 ..