connecting the dots

문제 풀이 DP사용. DFS로 푸는 사람도 많았다. 날짜를 1에서 시작하는 것보다 N에서 시작하는게 코드 구현이 더 간단하다. 경우 1. 날짜 i에 상담을 진행한 경우 -> dp[i]=dp[i+t[i]]+p[i] 2. 날짜 i에 상담을 진행하지 않은 경우 -> dp[i]=dp[i+1] 22번째 line에서 dp[i]=0; 로 작성해서 틀렸었다. 나와있는 테스트케이스는 모두 맞췄는데, 다른 부분에서 조건이 위배됐나 봄.. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include #include #include using namespace std; int main(){ int dp[2..

풀이 이차원배열 DP[N][K]를 기반으로 한다. DP[i][j]=DP[0][j-1]+DP[1][j-1]+ ... +DP[i][j-1] 점화식을 세웠다. for문 돌리기 전 배열 값 설정을 잘못했더니 오류 발생함. 중간에 1,000,000,000 나머지 값 저장하는 것도 잊지 않기. 코드 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include using namespace std; int main(){ int dp[201][201]={0}; int n, k; scanf("%d %d", &n, &k); for(int i=1;i

풀이 i번째 계단을 올랐을 때까지의 총 점수의 최댓값은 1. DATA[i] + DP[i-2] 2. DATA[i] + DATA[i-1] + DP[i-3] 중에서 MAX값을 구한 것이다. 예외) 마지막 계단인 n번째 계단은 꼭 올라야 하므로 n-1와 n-2 모두를 오를 수는 없다. 따라서, n-1번째 계단은 예외적으로 DP[n-1]=DATA[n-1]+DP[n-3] 이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include #include using namespace std; #define MAX 300 int main(){ int dp[MAX..

풀이 i번째 수의 가장 긴 증가하는 부분 수열 길이는 1. 1~i-1번째 중 i보다 값이 작으면서 2. 가장 긴 증가하는 부분 수열의 길이가 max인 값 보다 1이 크다. 중간에 max=0을 안해주고 계속 반복문 돌렸더니 오류가 발생함. 주의해야겠다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include #include #include using namespace std; int main(){ int numArr[1001],data[1001]; int maxNum; int n; scanf("%d", &n); for(int i=1;i