소프트웨어개발블로그 소프트웨어개발블로그

풀이 # 무조건 큰 제곱수를 빼는것이 최소 횟수가 아니다. 67 = 64 + 1 + 1 + 1 --> 4개 67 = 36 + 25 + 4 --> 3개 즉, 67 보다 작은 제곱근들 (1, 4, 9, 16, 25, 36, 49, 64) 에 대하여 1. 67 - 1 로 시작하는 경우2. 67 - 4 로 시작하는 경우3. 67 - 9 로 시작하는 경우...8. 67 - 64 로 시작하는 경우 를 모두 알아보아야 한다. "DP[N] = N 의 최소 제곱수의 합의 개수" 라고 한다면 DP 배열이 1 ~ N 까지 채워져 나가는 반복문 안에서 ---> i1 ~ (i*i) 의 제곱수를 빼나가며 최소값을 찾는 과정이 들어가야 한다. ---> j 점화식은 for (i = 1; i > N; for (i = 1; i

풀이 3. 마지막 도착 계단은 반드시 밟아야 한다. 이 규칙이 가장 중요하다. ... 15 25 10 20 or ... 25 10 20 이 두가지 중 하나는 무조건 선택이 될 것이다. 즉, 다음과 같이 요약될 수 있다. 1. 마지막 직전을 선택한 경우2. 마지막 -2 번째를 선택한 경우 결과적으로 이 두값의 크기를 비교하여 큰 값에 마지막 숫자를 더해주면 된다. 점화식은 DP[N] = max( DP[N-3] + arr[N - 1] , DP[N - 2] ) + arr[N] 이 된다. 코드 @github 에서 보기 /** * @site: https://www.acmicpc.net/problem/2579 * @github: https://github.com/7772 * @auth: Landon Park * @..

풀이 연속합 문제는 3중 for 문을 구성해야 풀 수 있다. 기억할 연산값을 저장하는 DP 배열에 10 10 + -4 10 + -4 + 3 ... -4 -4 + 3 -4 + 3 + 1 ... 12 12 + 21 12 + 21 + -1 이렇게 모든 값을 비교해보려면 3중 for 문이 필요했다.. 그러나 1 개의 생각만 하면 하나의 for 문으로 문제를 해결할 수 있다. 값을 더해나가는 sum 값이 음수이면 초기화 시킨다. 이전 까지 아무리 큰 값이 나왔더라도 다음에 나올 값이 음수라면 지금까지 더한 값은 최대값이 될 수 없기 때문이다. 해답을 보고나니 너무나 당연한 이론인데 왜 생각해내지 못했을까 싶었다. 코드 @github 에서 보기 /** * @site: https://www.acmicpc.net/pr..

풀이 증가하는 부분수열 문제를 2 번 이용해서 해결할 수 있다. 첫번째는 왼쪽에서 오른쪽으로 진행하면서 증가하는 부분수열을 찾는다. 두번째는 오른쪽에서 왼쪽으로 진행하면서 증가하는 부분수열을 찾는다. 위와 같이 계산이 되는 것을 볼 수 있다. 여기서 최대값 8 이 정답이라고 생각할 수 있다. 그러나 잘 생각해보면 최대값 8 은 1 2 3 4 5 의 증가 부분과 5 2 1 의 감소부분의 합으로 이루어져있다. 여기서 5 가 중복되기 때문에 최대값에서 - 1 을 해주어야 올바른 값이 나온다. 코드 @github 에서 보기 /** * @site: https://www.acmicpc.net/problem/11054 * @github: https://github.com/7772 * @auth: Landon Park..

풀이 앞선 11053, 11055 문제 들과 똑같은 문제이다. 다만, 코드를 그대로 가져오기 보다는 복습을 한다는 생각으로 알고리즘을 처음부터 다시 생각해보며 풀어보길 바란다. 부등호 방향만 바꿔주면 된다는 것을 알 수 있다. 코드 @github 에서 보기 /** * @site: https://www.acmicpc.net/problem/11722 * @github: https://github.com/7772 * @auth: Landon Park * @date: 2018. 08. 03 */#include using namespace std; int main() { int DP[1001]; int arr[1001] = { 0, }; int T; int i, j; int max = 1; cin >> T; fo..

풀이 DP 문제를 풀어가면서 가장 중요하다고 느낀 점은 "DP 배열을 어떻게 표현할 것인가" 이다. 지금까지의 DP 문제들은 "DP[x] = 문제에서 요구하는 x 의 결과값" 이었다. 즉 최종적으로 구하고 싶은 값이 x 이어도 DP 배열은 DP[x - y] 에 대하여 해당 x - y 에서의 문제가 요구하는 결과값을 담고 있도록 구성하였다. 그러나 이 문제들은 다르다. DP 배열은 각각 대응되는 결과값으로 초기화 시킨다. 즉, 가장 긴 부분수열 문제의 경우에 10 20 10 30 20 50 의 입력값에 대하여 DP 배열은 idx 1 ~ 7 까지 모두 1 로 초기화 되고 만약 조건을 통과하지 못하면 최종적으로 그대로 1 로 남는다. 이건 아주 큰 차이인데, 좀더 자세히 다음을 보면서 설명해보겠다. 10 20..

풀이 2번 규칙을 보자. 연속으로 놓여있는 3잔을 모두 마실 수는 없다. 이 말은 다음과 같은 것은 가능하다는 것이다. 1. 안마신다. 2. 1 번 연속 마신다. 3. 2 번 연속 마신다. 그리고 DP 배열은 다음과 같이 구성한다. DP[포도잔의 수] = 정답 그렇다면 이 예제의 경우에서 6 10 만이 입력된다면 DP[2] = 16 이다. 만약 6 , 10 , 13 만이 입력된다면 DP[3] = 23 이다. 여기에서 알 수 있는 것은 포도주 3 잔의 최대값을 알려면 3개의 값을 비교해야 한다는 것이다. DP[3] = max ( 6 + 10 , 10 + 13 , 6 + 13 ) = 23 이 식은 또 이렇게 바꿀 수 있다. DP[3] = max ( DP[2] , arr[2] + arr[3] , DP[1] +..

풀이 한 스티커를 사용한 후 좌/우/상/하 에 위치한 스티커를 사용할 수 없다면 이동할 수 있는 위치는 대각선 뿐이다. 이러한 특징을 이용하여 문제를 풀어야한다. 규칙 1. 스티커 위치의 이동은 대각선으로 한다. 그 다음은 한번에 몇칸까지 이동할 수 있는가를 고려해봐야 한다. 이렇게 한번에 1칸, 2칸, 3칸 ... 등을 움직였을때 2 X N 의 최대 가중치가 어떻게 달라지는지 파악하는 것이 중요하다. 위 그림은 70 까지 가는 2가지 방법을 나타내었다. 파란색 : 50 에서 바로 70 으로 이동, 50 + 70 = 120 빨간색 : 30 과 10 을 거쳐서 70 으로 이동, 30 + 10 + 70 = 100 빨간색은 2 번 이동했음에도 불구하고 1 번 이동한 파란색 보다 값이 작다. 항상 이런 결과가 ..