생각하는 아져씨

14501번: 퇴사https://www.acmicpc.net/problem/14501문제 정의상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오. 접근 방법[나이브한 방법] 1일 상담 -> 4일 상담 -> 5일 상담 2일 상담 3일 상담 -> 4일 상담 -> 5일 상담 4일 상담 -> 5일 상담 5일 상담 모든 경우를 구해서 N개를 N번 순회 -> O(N^2) [Dynamic Programming 접근 1] 그런데, 살펴보니까 n일 상담 이후의 과정이 동일함을 알 수 있다. 즉, 1일 상담 -> 4일 상담은 무조건 4일 상담-> 의 과정과 동일하다. 1일 상담 + 4일 상담 이후~ 4일 상담 + 5일 상담 이후~ 이런식으로 진행된다. 1, 2, 3, 4, 5, 6, ..

1912번: 연속합https://www.acmicpc.net/problem/1912 문제 정의n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 접근 방법다이나믹 프로그래밍 문제임을 알고 있어서 DP 테이블을 어떻게 정의해야 할까 고민했다.예제를 보면서 규칙을 찾으려고 했다. 연속합이므로 연속적인 숫자의 합이니까 이전의 값을 활용해야지 라는 생각으로 접근했는데, 생각보다 정의하기 어려웠다. 다이나믹 프로그래밍이 맞지만, ..

9461번: 파도반 수열https://www.acmicpc.net/problem/9461 문제 정의오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오. 접근 방법규칙을 찾고 점화식을 세우는 다이나믹 프로그래밍을 이용한다. 문제 해설규칙을 찾으면 N=6부터 점화식을 세울 수 있다.dp[i] ..

https://school.programmers.co.kr/learn/courses/30/lessons/42895 문제 정의어떤 숫자 N과 numbers가 주어질 때, N과 사칙연산만 사용해서 numbers를 표현해야 한다.이 때 N 사용횟수의 최솟값을 리턴해야 한다. 접근 방법다이나믹 프로그래밍 문제임을 알고 있어서 dp 테이블을 어떻게 정의해야 하는지 고민하다가 처음에는 다음과 같이 정의했다.dp[i]: i를 만드는데 필요한 N의 최소 개수 N = 5일 때, dp[0] = 0, dp[1] = 5/5 → 2, … dp[5] = 1 그리고 점화식으로는, dp[i] = min(1~(i-1) 중 더해서 i가 되는 조합의 숫자에 해당하는 인덱스의 dp 값) 즉, dp[7] = min(dp[1] + dp[6],..