본문 바로가기

Algorithm

백준 1699 제곱수의 합 Java 2019. 4. 15. 정답률 41퍼센트의 dp 문제이다. 왜 41퍼센트인지 모를 정도로 점화식 세우기가 어려웠다.. 마지막 자리에 올 수 있는 수는 1^2, 2^2, 3^2 등등 어떤수의 제곱인 i^2이다. 그리고 i^2 앞에는 n-i^2이다. 뒤에 i^2이 왔으니 n에 i^2을 빼야 하는 것이다. 그리고 dp배열에는 최종적으로 항의 개수가 들어가야 한다. 최종적으로 식은 n-i^2+i^2이므로 항 n-i^2에 +1을 해줘야 한다. 무슨소리인지 이해하기 힘들지만 이해하려고 하면 이해가 된다. 그렇게 점화식을 세우면 dp[n] = Math.min(dp[n-i^2]+1) //가능한 i범위 중에서 최소값 저렇게 세워진다. 1 2 3 4 5 6 7 8 9 10 11 12 13 public static void main(String[..
백준 2579 계단오르기 Java 2019. 4. 14. 정답률 38퍼센트의 dp문제이다. 백준에서 많이 풀려진 dp문제 중 하나이다. 다음 다음 계단으로 한번에 오르거나 다음 계단으로 오르거나 둘 중에 하나이다. 그리고 계단을 세 번 연속으로 오를 수 없다는 조건이 있다. n-1에 올 수 있는 경우에 수는 두 가지 있다. 두 번 연속으로 오른 경우와 첫 번째 계단인 경우 첫 번째 계단인 경우는 바로 전 계단을 오르지 않았을 경우다. 그렇기 때문에 전 전 계단 값 + 현재 값이다. dp[n] = dp[n-2]+값[n] 두 번째 계단인 경우는 현재 계단 값 + 전 계단 값 + 전전전 계단값을 더해야 한다. 여기서 현재 계단 값과 전 계단 값을 dp배열에서 더하지 않고 입력 받은 값이 들어있는 배열에서 더해 줌으로 써 세번 연속으로 계단을 오르지 않는다는 규칙을 ..
백준 1912 연속합 Java 2019. 4. 12. 정답률 26퍼센트의 dp 문제이다. 연속으로 된 몇 개의 수중 가장 합이 큰 값을 구하는 문제이다. 점화식을 구하는 방법을 보면 dp [i]에 올 수 있는 값은 dp[i-1]+값[i]이다. 하지만 값들 중에서 음수가 있기 때문에 dp[i-1]+값[i] 보다 그냥 값[i]가 더 클 수가 있다. 그래서 dp[i] = Math.max(dp[i-1]+값[i], 값[i]);로 점화식을 짤 수 있다. dp[i]엔 연속된 합들이 들어가게 된다. 현재 값과 전에 값을 더했는데 현재 값 보다 작은 경우엔 dp[i]에 그냥 원래 값이 들어간다. 이렇게 구한 dp배열 중 최대 값을 출력하면 된다. 코드는 몇 줄 안되는데 생각하기가 참 어려운 문제이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 p..
백준 11053 가장 긴 증가하는 부분 수열 Java 2019. 4. 12. 굉장히 유명한 문제라고 한다. 정답률은 37퍼센트 이다. 다이나믹으로 안풀어도 될 것 같아서 시도했다가 수 많은 반례에 짓밟혔던 문제이다. 최대값이 꼭 배열의 마지막에 있는 것이 아닌 10 50 10 20 30 40 이런식으로 예제가 입력 되는 경우도 있기 때문에 다이나믹 프로그래밍으로 풀어야 한다. 이 문제는 dp배열에 i번째에서의 길이를 넣어주면 된다. 10 20 10 30 20 50 이면 dp[1] (20)은 2이고 dp[3] (30)은 3이다. 숫자가 하나만 있어도 길이는 1이기 때문에 dp배열은 전부 1로 초기화 한다. 반복문 2개로 수열[i]보다 작은 범위의 수열[j]를 훑어서 수열[i]보다 값이 작으면 dp[j]를 본다. dp[j]가 dp[i]보다 값이 크거나 같다면. dp[i] = dp[j..
백준 2156 포도주 시식 Java 2019. 4. 10. 정답률 34퍼센트의 dp문제 포도주 시식이다. 1부터 n번까지의 포도주를 3잔연속으로 마시지 않는 규칙을 지키고 마실 수 있는 포도주 양의 최대값을 구하는 간단한 문제이다. 하지만 점화식은 간단히 생각할 수 없었다. 항상 마지막자리의 앞자리에 어떤 수들이 올 수 있는지를 생각해야 한다. 알면서도 틀리는건 왜일까. 쨋든 이 문제에서 마지막 자리인 n번째에 올 수 있는 경우의 수는 세가지이다. 1. 안 마실 때 2. 한 번 연속으로 마시는 잔일 때 3. 두 번 연속으로 마시는 잔일 때 세 번 연속으로 마시는 잔일 때는?이라고 생각할 수 있지만 점화식을 통해 세 번 연속으로 마시지 않게 처리하는 것이다.. 1. 안 마실 때 dp[n] =dp[n-1]; 안마시니까 그 전 잔의 값을 가져오면 된다. 2. 한 번 ..
백준 9465 스티커 Java 2019. 4. 10. 정답률 47퍼센트 dp문제인 스티커이다. 난 어려웠는데 정답률이 꽤 높은걸 보면 잘하는 사람들이 참 많구나 싶다. 이 문제는 이렇게 풀어야 한다고 한다. 스티커가 올 수 있는 경우에 수에 따라 dp[n][]배열을 만들어 준다. 첫 번째 경우인 dp[n][0]은 X X 두 개 다 때지 않은 경우 두 번째 경우인 dp[n][1]은 O X 위쪽을 땐 경우 세 번째 경우인 dp[n][2]는 X O 아래쪽을 땐 경우이다. 이렇게 해서 점화식을 생각해내면 된다.. 첫 번째 경우엔 둘 다 때지 않았기 때문에 n-1에 세가지 경우가 모두 와도 상관이 없으므로 dp[n][0] = Math.max(dp[n-1][0], Math.max(dp[n-1][1], dp[n-1][1])); 두 번째 경우엔 위쪽을 땠기 때문에 n-1..
백준 11057 오르막 수 Java 2019. 4. 10. 정답률 47퍼센트의 dp 문제 오르막 수 이다. 백준 10844 쉬운 계단 수 Java dp배열을 1차원 배열로만 만들어서 쓰다가 2차원 배열로 만들어 써야하는 첫 번째 문제였다. 애초에 2차원 배열로 접근해야 하는지도 생각해내지 못했다. dp[길이 n][마지막 자리 수]로 접근해야 한다. n이 1일.. dundung.tistory.com 앞서 글을 썼던 쉬운계단 수 문제와 굉장히 비슷한 문제이기 때문에 정답률이 높은 것이라는 추측을 한다. 차이점이 있다면 쉬운 계단 수는 마지막 자리에 있는 수에서 반드시 1차이가 나야했지만 오르막 수는 자신을 포함한 자신보다 큰수여야 한다. 예를 들면 마지막 자리 수가 8이면 8,9가 해당 된다. 쉬운 계단 수와 똑같이 점화식을 세우면 dp[n][마지막자리 수] = d..
백준 10844 쉬운 계단 수 Java 2019. 4. 10. dp배열을 1차원 배열로만 만들어서 쓰다가 2차원 배열로 만들어 써야하는 첫 번째 문제였다. 애초에 2차원 배열로 접근해야 하는지도 생각해내지 못했다. dp[길이 n][마지막 자리 수]로 접근해야 한다. n이 1일 땐 {1, 2, 3, 4, 5, 6, 7, 8, 9} 한자리이기 때문에 쉬운 계단 수가 총 9개 이고 dp[1][i] = 1 일 것이다. n이 2일 땐 {12, 21, 23, 32, 34 ...} 일것이고 dp[2][2] 일 때를 생각해보면 {12, 32} dp[2][2] = 2일 것이다. 쉬운 계단 수는 차이가 1이 나는 것만 가능하기 때문에 미리 구해둔 dp[n-1]에서 [마지막 자리수+1] 과 [마지막자리수-1]을 해준 값을 더해주면 되는 것이었다. 따라서 점화식은 dp[n] = dp[n..

티스토리툴바