알고리즘!76 [C] 2156: 포도주 시식 처음에 점화식을 쉽게 찾았고 구현도 다른 DP 문제처럼 쉽게 되서 완전 쉽게 풀줄 알았다... 점화식은 쉽게 보면 근데 여기서 간과한 점이 다른 "계단 오르기"문제와의 차이점이 있다는 것인데 그건 바로 와인을 안마셔도 된다는 것이었다..! 예를 들어 (6) 100 100 1 1 100 100의 최대 포도주 양은 계단 오르기 문제에서는 301이지만 여기서는 400이 된다. 3번째와 4번째에서는 안마시는게 이득이다. 따라서 if(dp[i]=2) { dp[2]=dp[1]+arr[2]; cnt=2; //연속 두잔을 마심 max=dp[2]; } if(n==3) { if(arr[2]>arr[1]) dp[3]=arr[2]+arr[3]; else { dp[3]=arr[1]+arr[3]; cnt=1; } max=dp[3.. 2023. 7. 24. [C] 9461: 파도반 수열 실제 파도반 수열이 뭔지는 모르겠지만 원래 수열은 모르겠으면 쓰면 되는데 이것도 그림 보면서 수열을 적다보니 쉽게 규칙이 보였다! 수열이 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37... 이런 식으로 증가하는데 각 수열의 항끼리 차를 통해 증가하는 값을 계산해보면 0 0 0 1 0 1 1 2 2 3 4 5 7 9... 이런 식으로 증가한다. 자세히보면 6번째부터 5개 전의 항만큼 더해지는 것을 알 수 있다. 즉., dp[i]=dp[i-1]+dp[i-5]라는 점화식을 쉽게 더해질 수 있다. 그리고 여기서 조심해야하는 점은 100번째 항이 int형 범위로는 표현할 수가 없어 long long int로 지정하여 문제를 풀 수 있었다. 항상 범위를 조심하고 떄에 맞는 자료형을 써야겠다. 여러 .. 2023. 7. 23. [C] 1912: 연속합 이 문제도 전형적으로 dp[]라는 배열을 선언하여 각 순간마다 가장 이득인 경우를 배열에 넣어준다. 코드 설명에도 나와있지만 부분합이 0보다 작아지게 된다면 다시 시작하는게 이득이고 0보다 크다면 계속 이어나가는게 이득이다. 하지만 이때도 부분합이 여러개 생길 수 있는데 이 부분합중에 최대인 것을 저장하기 위해 max라는 변수를 이용해야한다. 이 문제를 풀때 자꾸 54%에서 실패가 났는데 알고보니 arr[]의 값이 0일때 max가 되는지 비교를 안해줘서 나타나는 오류였다. 더 치밀하게 비교하고 계획하는 연습을 해야겠다 전형적인 문제라 계획을 짜는데는 큰 시간이 들지 않았고 dp배열과 arr배열을 헷갈리지 않고 정확하게 쓰는 연습을 조금 더 해야할 것 같다. 또한 전에 정리해놓기는 했지만 최대값,최솟값과 .. 2023. 7. 23. [C] 1932: 정수 삼각형 이 문제 역시 Dynamic Programming! 역시 규칙찾아 점화식을 구하면 쉽게 풀 수 있다 규칙은 자기 위층의 양 옆까지 수까지의 경로에 있는 수의 합을 저장하는 것하면 되는데 여기서 주의해야 할 것은 각 층의 양끝은 무조건 바로 위쪽 한군데에서만 따로 내려오므로 점화식에서 예외처리를 해줘야한다. 예외처리를 굳이 하고 싶지 않다면 전에 풀었던 Knapsack Problem처럼 배열 양 끝에 0을 추가해주면 한번의 정리가 가능하다. 처음에 이 문제를 풀 때 잘못 이해하여 배열을 500!만큼 잡야아하는줄 알고 재귀함수를 이용해 각 함수를 호출할 때마다 배열의 크기가 최대 500만큼 되도록 잡았는데 사실 이차원배열을 이용하면 최대 250000의 크기를 잡아도 되어 범위였다! 그래서 이차원 배열을 잡고.. 2023. 7. 23. 이전 1 ··· 13 14 15 16 17 18 19 다음