문제 이해 단계 https://www.acmicpc.net/problem/2579 입력으로 계단의 개수가 주어지고, 그다음부터 각 계단의 점수가 순서대로 주어진다. 출발부터 시작하여 마지막 계단까지 이동하는데 2가지 규칙을 따른다. 1. 이동은 1칸 또는 2칸을 이동한다. 2. 1칸을 이동할 때는 연속되는 3칸을 이동할 수 없다(1,2,3 이런 식) 이런 조건에서 마지막 칸까지 이동할 때 얻을 수 있는 최대 점수를 구하는 문제이다. 문제 접근 단계 마지막 계단을 무조건 밟아야 하기 때문에 마지막 계단부터 생각해 보자. 마지막 계단으로 도달할 수 있는 경우의 수는 2가지가 있다. 1. 1칸 이동했을 때 2. 2칸 이동했을 때 그런데 우리가 구해야 하는 것은 마지막 계단에 도착했을 때의 최대 점수이다. 때문..

문제 이해 단계 https://www.acmicpc.net/problem/1010 N과 M이 주어진다. N = x; i--) { result += dp(x - 1, i - 1); } d[y - x][y] = result; return d[x][y] = result; } 핵심이 되는 dp함수이다. 매개변수로 N, M을 뜻하는 x, y를 받는다. 2차원 배열 저장공간 d [][]를 사용하여 해당 경우의 수를 저장해 놓는다. long long int로 선언한 이유는 값이 엄청나게 커질 수 있기 때문에 오버플로우 발생을 방지하기 위해서이다. 우선 빠른 연산을 위해 N이 1이 경우와 N과 M이 같을 경우는 연산이 쉬우므로 그 결과는 바로 배열에 담아 반환한다. 그리고 이미 연산결과가 있는 경우에는 계산하지 않고 ..

문제 이해 단계 https://www.acmicpc.net/problem/9466 1~n번까지 사람이 있고 선택을 한다. (자기 자신도 선택 가능) 조가 이루어지는 경우는, 꼬리 잡기처럼 1 -> 2 -> 3 -> 1 이런 식으로 사이클을 이를 경우이다. 즉, 마지막에는 자기 자신으로 꼭 돌아와야 한다. 이러한 조건일 때, 짝을 이루지 못한 학생 수를 출력하는 문제이다. 문제 접근 단계 문제 이해 단계에서 말했듯이, 꼬리 잡기와 비슷한 패턴이다. 꼬리에 꼬리를 물어 추적을 하는 것이다. 이를 돌려 말하면 점점 깊이 들어간다고 할 수 있는데, 그래서 이 문제는 DFS로 푸는 것이 적절하다고 생각했다. 이 문제에서 짝이 이루어지는 경우는 사이클이 형성될 때이다. 처음 선택했던 사람의 번호를, 마지막 사람이 ..

문제 이해 단계 입력값으로 N이 입력된다. 선택할 수 있는 봉지는 3kg와 5kg이다. 이 봉지들을 이용하여 정확히 Nkg을 나눠 담을 때 가장 적은 봉지가 나오게 하는 문제이다. 문제 접근 단계 현재에서 가장 이득이 되는 선택을 하는 그리디로 풀 수도 있지만, 다이나믹 프로그래밍(DP)으로도 풀 수 있다. 왜냐하면, 작은 부분에서의 답이 큰 부분의 답이 되기 때문이다. N = 15 일 때를 가정해 보자. 15kg는 12 + 3 또는, 10 + 5에서 만들어진 숫자이다. 즉 12,10에서 만들어진 숫자인데, 12와 10은 (9,7), (7,5)에서 만들어진 숫자이다. 이런 식으로 작은 부분의 연산값이 큰 부분의 값이 된다. 이런 특징을 띄고 있기 때문에 DP로 풀 수 있다는 것이다. N에서 가장 적은 봉..

문제 이해 단계 2차원 격자가 주어지고, 각 정점의 연결 정보들이 주어진다. 시작 위치 S와 도착 위치가 E가 주어졌을 때 S에서 E로 가는 최단 거리를 구하고, 그 후 S에서 E로 갔을 때, 방문하지 않았던 정점만을 사용하여 다시 E에서 S로 최단거리로 돌아간다. 이때의 최단 거리의 합을 구하는 문제이다. 문제 접근 단계 해당 문제를 어떻게 푸는지에 대한 키워드는 1. 최단 경로의 거리를 구한다는 것 2. 산책을 할 수 있는 경로의 데이터만 주어진 다는 것이다. 1번의 키워드에서 경로를 탐색하여 최소 횟수를 찾는 DFS나 BFS를 사용해야 한다는 것을 알았다. DFS와 BFS 중 어떤 것으로 풀어야 효율적 일지 고민 중이었는데 2번 키워드에서 힌트를 얻었다. 산책을 할 수 있는 경로만 주어진다는 것은 ..

문제 이해 단계 https://www.acmicpc.net/problem/22948 문제는 앞서 풀었던 원 이동하기 1과 똑같다. 문제에 대한 자세한 설명은 원 이동하기 1에 대한 링크를 달아둘 테니 참고해 주길 바란다. https://howudong.tistory.com/33 [C++] 백준 22946 - 원 이동하기 1 문제 이해 단계 문제 좌표평면에 N개의 원이 존재한다. N개의 원 중 임의의 두개의 원을 선택했을 때 내접, 외접 등 교점이 존재하지 않도록 존재한다. 하나의 원이 다른 원 안에 포함될 수는 howudong.tistory.com 이 문제에서 다른 점은 두 원을 지정해 준다는 점과 원 번호,x좌표,반지름이 입력으로 주어진다는 점이다. 그리고 출력으로 이동횟수와 더불어 이동한 원의 번호를..

문제 이해 단계 https://www.acmicpc.net/problem/16973 NxM 크기의 격자판이 주어지고, 크기가 HxW인 직사각형이 주어진다. 이동할 수 있는 칸은 0, 이동할 수 있는 칸은 1로 되어 있다. 직사각형의 가장 왼쪽 위의 칸이 처음에 주어지고, 도착 좌표가 주어진다. 이때 이 직사각형의 왼쪽 위가 도착좌표까지 갈 때 최단거리를 구하는 것 문제 접근 단계 직사각형의 크기가 있다는 점만 제외하고는 벽과 격자판이 존재한다는 점과 특정 지점까지 이동하는 최단 거리를 구해야 한다는 점에서 대표적인 BFS 문제라는 점이라는 것을 알 수 있다. 중요한 것은 직사각형이기 때문에 체크해야 할 부분이 하나가 아니라 여러 개로 늘어났다. 직사각형 왼쪽 위 칸이 도착 지점으로 가야 하므로, 이 문제..

문제 이해 단계 https://www.acmicpc.net/problem/22946 좌표평면 안에 N개의 원이 존재한다. (1)N개의 원은 모두 겹치지 않는 상태거나, (2)한 원이 다른 원이 내부에 속하거나 (3)두 원이 만나지 않는 경우 로만 존재한다. 이때, 하나의 원 내부에서 다른 원의 내부로 이동하는데, 한 원당 딱 한 번만 방문 가능하다. 좌표평면도 하나의 거대한 원으로 취급하여 방문 가능하다. 이런 조건일 때 한 원에서 다른 원으로 이동할 때, 얻을 수 있는 최대 이동 수를 얻는 문제이다. 문제 접근 단계 한 원을 기준으로 다른 원을 비교한다고 생각했을 때, 두 가지 상태로 밖에 존재하지 않는다. 내부에 있거나 외부에 있거나 둘 중 하나의 경우이다. 위의 문제 조건에서 한 원당 한 번씩밖에 ..