Go Gradually - Repository

1301. Number of Paths with Max Score - Streak 6

DP 로 최댓값을 유지하면 풀 수 있다. 근거: 해당 지점의 최댓값이 바뀌면, 이후는 반드시 그 최댓값 경로를 따라야 한다.따라서, 비교적 간단하게 최적 부분 구조+중복 부분문제를 만족한다. 그럼 남은 문제는, "벽 의 처리를 어떻게 할 것인가?"이다.그냥 초깃값을 매우 낮은 음수로 설정해두면 된다.1만 * 9 = 최대 값 9만이니, 기본 값 초기화를 전부 -10억으로 해두면 벽을 뛰어넘는 값으로 잘못된 값을 리턴하기 어려워진다.class Solution { public int[] pathsWithMaxScore(List board) { int n = board.size(); List> dp = new ArrayList(); for(int i = 0; i tem..

1250. Check If It Is a Good Array - Streak 5

이 문제는 결국 양수와 음수의 조합으로 나타내진다.이를 모듈러 연산으로 나타낼 수 없을까? 여기서 확장 유클리드 호제법이 적용 가능해진다.gcd = 1인 조합이 하나라도 있으면 True이다.근데 우리 문제는, 다음과 같은 형태이다.이걸 확장 유클리드 호제법의 형태로 바꿀 수 없을까?둘을 더하면, 최대공약수는 약수로 남기고, 나머지는 더한 효과가 된다.즉, 둘을 더해도 최대공약수는 무조건 남는다 최대공약수는 이 문제에서 지워야 하는 대상이므로,전체의 최대공약수가 1이면 True이고, 전체의 최대공약수가 1이 아니면 False이다.class Solution { public boolean isGoodArray(int[] nums) { int now = nums[0]; for(in..

1000. Minimum Cost to Merge Stones - Streak 4

비슷한 문제를 풀어본 적이 있다.https://www.acmicpc.net/problem/11066 이 문제와 다른 것은 뭘까?파일 합치기는 반드시 바로 옆칸 1개와 합치기 때문에, 순차대로 순회하기가 쉽다.이 문제는 연속된 k칸끼리 합쳐야 하기 때문에, 추가적인 처리가 필요하다.n%(k-1)==1 이 아니면 -1을 반환해야 한다.연속된 k칸끼리의 합치는 방법을 생각해야 한다.파일 합치기의 경우DP[i][j] = DP[i][k] + DP[k+1][j] + psum[j] - psum[i-1]이 문제는?연속된 k칸을 합쳐야 한다. 점화식 자체가 달라지는건가?dp[i][p] + dp[p][q] + ...k가 커지면 for문의 깊이도 그만큼 커진다.k가 2인 경우를 제외하고,내부가 len % (k-1) == 1..

내 풀이 접근현재 인덱스까지 구할 수 있는 최대 수익을 계산하려면이전 인덱스에 담겨 있는 최대 수익과, 그 인덱스부터 지금까지의 1회 최대 수익을 알고 있어야 한다.이는 카데인 알고리즘과 굉장히 유사하다고 판단했다. 따라서 DP를 이용해 현재 인덱스까지 가장 최적의 이익을 찾도록 했다.class Solution { public int maxProfit(int k, int[] prices) { int[][] dp = new int[prices.length + 1][k+1]; int ret = 0; for(int kk = 1; kk이래도 통과는 한다.하지만, 조건이 빡빡하다면 통과하지 못했을 것이다.좀 더 효율적인 해이전에 구할 수 있는 최대 이익을, 0~i까지 전..