문제 이해 단계 수학에서 조합을 뜻하는 nCr에서 n과 r이 입력으로 들어올 때, 그 해답을 출력하는 문제. 문제 접근 단계 일반적으로 연산식을 구현하여 계산하라고 이 문제를 냈을 리는 없다. 예제에서 봤듯이 입력애 따라 출력이 엄청 커지는데, 연산 처리가 오래 걸려 시간초과가 뜰 가능성이 높다. 그래서 조합 공식 nCr = n-1Cr + n-1Cr-1을 메모라이즈기법(DP) 방식으로 구현하기로 하였다. d [n][m]라는 2차원 저장공간을 두고 nCr = d [n][r] 이런 식으로 연산 값을 기억해 두기로 하였다. 그런데 한 가지 문제가 생겼다. 바로 연산 값이 엄청나게 크다는 것이다. 가장 큰 자료형인 long long int가 –9,223,372,036,854,775,808 ~ 9,223,372,..

문제 이해 단계 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다. 자연수 n이 주어질 때, 최소 개수의 제곱수 합, 즉 최소한의 자연수를 사용하여 구하는 문제이다. 문제 접근 단계 제곱수라는 말과 반대되는 말은 루트이다. 4 = 2^2인데, 이때 제곱이 되는 2라는 값은 4의 루트를 씌우면 구할 수 있다. 여기서 5라는 값을 살펴보면 5의 루트를 씌우면 2.xxx 자연수 부분은 2가 된다. 해당 문제에서는 5 = 2^2 + 1^2가 되어 2가 출력될 것이다. 이런 식으로 n에다가 루트를 씌어 하나의 제곱수를 구하고, 그 수를 뺀 나머지를 또 루트를 씌우는 과정을 반복한다면? 우리는 제곱으로만 이루어진 수의 합을 구할 수 있을 것이다(1^2이 있기 때문) 15라는 숫자를 예로 들어, 그림..

문제 이해 단계 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좌표,반지름이 입력으로 주어진다는 점이다. 그리고 출력으로 이동횟수와 더불어 이동한 원의 번호를..