케이스윔의 개발 블로그

문제각 배열의 원소가 주어지고, 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를 이용해야했습니다. 처음엔 전.혀 감이오지 않아서 넘겨버렸던 문제였는데 그림을 그려서 생각해보니 쉽게 생각할 수 있었..

문제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개로 만들었다면 거기에다가 ..

문제서쪽의 N개의 사이트, 동쪽의 M개의 사이트가 주어질 때 다리를 놓을 수 있는 경우의 수를 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/1010) 풀이꽤 간단한 문제인데 (혼자) 함정아닌 함정에 빠져서 1시간정도 걸린 문제입니다. 동쪽에 M개의 사이트로 N개의 다리를 놓는 경우의 수이고 모든 다리는 똑같이 생겼을 것이기 때문에 조합의 수와 같다고 할 수 있습니다. 처음에 생각을 하지 않고 풀었는지 이 문제가 dp일까? 하면서 조합을 구하는 공식 n!/k!(n-k)! 을 바로 적용해버렸습니다. 테스트케이스는 올바르게 나왔지만 신중히 제출하기 위해 질문검색을 찾아보니 바로 오버플로우가 나는 것을 알 수 있었습니다. N, M이 30이하이지만 30!만 해도 ..

문제N개의 원소를 가지는 수열이 주어졌을 때 가장 긴 증가하는 부분 수열의 크기를 구하시오.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/11053) 풀이DP를 통해 풀 수 있는 문제입니다. DP문제는 생각이나 구현면에서 다른 알고리즘에 비해 시간이 적게 걸린다는 장점이 있어서 요즘 공부를 하다가 집중이 안될 때 풀고 있는 중입니다! 풀이를 안적어도 될 정도로 간단한 문제들이 많지만 오랜만에 적어보겠습니다. 이 문제에서는 수열이 주어지고 가장 긴 증가하는 부분 수열을 구해야하기 때문에 두조건을 만족하는 경우 큰수가 dp배열에 저장될 수 있도록 했습니다. nums[i], dp[i] 라는 배열을 만들었고 nums에는 입력받은 값이 들어가있습니다. dp[i]의 값은 n..

문제제일 왼쪽 위칸에서 제일 오른쪽 아래칸까지 갈 수 있는 경로의 수를 구해야한다. 각 칸에는 점프할 수 있는 거리가 적혀져있고 오른쪽 또는 아래쪽으로만 점프할 수 있다.문제출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1890) 풀이처음에는 BFS로 접근했었다. 첫 칸을 큐에 넣어준다음 while문을 통해서 큐에 값을 빼내고 해당하는 위치에서 갈 수 있는 칸들을 큐에 넣도록 했다. 처음엔 모두 큐에 넣어버리고 (0, 0)을 시작으로 했을 때 (N-1, N-1)이 큐에서 나오면 카운트를 해주도록 했다. 그렇게 했더니 큐에 너무나 많은 경로들이 들어가서 메모리 초과가 났다. 메모리 초과를 해결하기 위해서 visited배열을 만들었고, 만약 이미 해당하는 칸에 이미 갔었다..

문제재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 숫자가 하나 써있다. i번째 칸에 써있는 숫자를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 써있는 숫자가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이 때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다. 입력첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 Ai (0 ≤ Ai ≤ 100)가 주어진다.출력은 재환이가 최소 몇 번 점..

문제효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다.효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 예를 들어 6개의 ..