프로그래밍 (31) 썸네일형 리스트형 [BOJ][DP] 11054. 가장 긴 바이토닉 수열 문제 -> https://www.acmicpc.net/problem/11054 이 문제 역시 바로 감이 온다. 가장 긴 증가하는 부분 수열 오른쪽, 오른쪽 -> 왼쪽 이렇게 두번의 연산을 각각 한 후 두 연산한 값을 모두 더해 제일 큰 것이 답이 되겠다. 여기서 주의해야 할 점은 왼->오. 오->왼 둘다 자기 자신을 포함한 상태이기에 결과를 출력할 때 무조건 -1을 해줘야한다. 소스(Github) [BOJ][DP] 9251. LCS 문제 -> https://www.acmicpc.net/problem/9251 이 문제도 아주 곤욕을 치뤘다. http://twinw.tistory.com/126 dp[i][j] = dp[i-1][j-1] + 1; 2) 알파벳이 다른 경우-> dp[i][j] = max(dp[i-1][j], dp[i][j-1]); 왜 위와 같이 나오는지는 위의 링크를 가서 설명을 보면 명쾌히 풀릴 것이다. 감사드립니다 White Whale님.. 소스(Github) [BOJ][DP] 11722. 가장 긴 감소하는 부분 수열 문제 -> https://www.acmicpc.net/problem/11722 이 문제 또한 가장 긴 증가하는 부분 수열의 풀이와 동일하다. 가장 긴 증가하는 부분 수열 -> http://tiredsleeper.tistory.com/33?category=782681 차이점이 있다면, 증가하는 부분 수열 문제에서는숫자[i] 보다 작은 수에 대해 dp값을 비교하는 것이었지만, 이번에는 거꾸로다.숫자[i]보다 큰 수에 대해서 dp값을 비교해야한다.감소한다는 것은 큰 값에서 작은값이 된다는 것이니. 소스(Github) [BOJ][DP] 11055. 가장 큰 증가 부분 수열 문제 -> https://www.acmicpc.net/problem/11055 가장 긴 증가 부분 수열 문제와 동일하게 접근하면 된다. 다만, 달라진 점은 길이가 아니라 합이라는 점. 아마 거의 소스가 동일할 것이다. 소스(Github) [BOJ][DP] 1699. 제곱수의 합 https://www.acmicpc.net/problem/1699 처음에는 문제에 대한 접근을 일단 될 수 있는대로 큰 제곱수 (x [BOJ][DP] 11057. 오르막 수 문제 -> https://www.acmicpc.net/problem/11057 이번 문제는 나름 참신하게 문제를 푼 것 같다?..어떤 누군가가 이렇게 풀이를 한 사람이 있을수도 있겠지만.. ======================================== 보통 3중 for문으로 일일이 dp값을 다 더하는 반면에, 나는 연산량을 줄이려고 다른 점화식을 생각해봤다.. dp[i][j] : i번째 자릿수에서 숫자 j가 만들어낼 수 있는 경우의 수 여기서 만들어 낼 수 있는 경우의 수라고 함은 숫자 j가 i+1번째 자릿수의 가능한 경우의수를 의미한다. dp[i][10] : i+1번째 자릿수의 모든 경우의 수 i-1 번째 자릿수의 가능한 경우의 수는 i번째의 숫자 0이 만들 수 있는 경우의 수와 같으므로 d.. [BOJ][DP] 11053. 가장 긴 증가하는 부분 수열 문제 -> https://www.acmicpc.net/problem/11053 오래 생각을 해도 기존에 했던 생각밖에 들지 않고참신한 방법이 들지 않는다. 결국 또 참고하게 됬다..무엇이 문제일까. ============================================= DP에서 유명한 문제라고 한다. 일일이 내 뒤에있는 값을 신경쓰며 비교하고 지지고 볶고 할 필요 없이, 현재 자기 자신보다 작은 값이 가지고 있는 길이(dp값) 중 제일 큰 것을 자신을 포함해서 더하면 된다. 처음에는 모두 0이다.첫번째 값인 10은 자기 자신밖에 없으므로 1. 두번째 20은 자기 앞에 자기보다 작은 수인 10이 존재한다.고로 그 10의 길이인 1을 더한다. 세번째 10은 자기보다 작은 수가 없어 그냥 자기 길이.. [BOJ][DP] 2293. 동전 1 문제 -> https://www.acmicpc.net/board/view/10754 금방 풀릴 것 같은 예감과 함께즐겁게 생각을 했으나.. 역시나. 오래걸렸다..결국 풀이를 참고할 수밖에 없었고.. DP를 이제 나름 꽤 푼 것같은데 실력이 안느는것일까... 각설하고. 1 ~ 10원까지 세 가지 동전을 조합하여 나오는 경우의 수를 DP 배열에 넣고,그 DP를 이용하여 계속 10원까지 계산한다는 식의 접근 방법을많이 떠올렸을 것이라 생각한다. (내가 이랬다) 위의 경우 중복을 고려하여 일일이 다 빼줘야하는데,그럴경우 재귀로 구현해야한다. 쉽게 코드 몇줄로 이 문제를 풀 수가 있는데, 사용자가 입력한 값들중에서제일 작은 값을 최대한 활용하여 나머지 입력 값들에 대한경우의 수를 구해줘야 한다. 문제에 있는 예제.. 이전 1 2 3 4 다음
