Problem Solving1217 [백준] 1699 제곱수의 합 - Dynamic Programming / Java • 문제 링크 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net • 풀이 과정 각각의 자연수 n 의 최대 제곱수의 갯수는 n 이므로, 반복문을 통해 제곱수의 최대 개수를 초기화한다.(dp[i] = i) 1 ~ 3 은 제곱수의 최솟값 또한 1 ~ 3 이며, 나머지는 아래와 같이 구할 수 있다. n 제곱수 점화식 개수 dp[4] 2^2 dp[4 - 2^2] + 1 = dp[0] + 1 1 dp[5] 2^2 + 1^2 dp[5 - 2^2] + 1 = dp[1] + 1 2 dp[.. 2022. 8. 26. [백준] 1912 연속합 - Dynamic Programming / Java • 문제 링크 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net • 풀이 과정 입력된 수열의 연속된 수의 합을 구하고(sum), 해당 값과 현재까지 구해진 연속된 수의 합(max) 의 최대값을 비교하여 갱신한다. 이때 합이 음수일 경우,(sum < 0) 다음에 연속된 수의 합은 해당 수보다 작으므로 sum = 0 으로 초기화하여 새로 합을 구한다. 이렇게 최종적으로 갱신된 max 값을 정답으로써 출력한다. • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWri.. 2022. 8. 25. [백준] 2193 이친수 - Dynamic Programming / Java • 문제 링크 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net • 풀이 과정 [백준] 10844 쉬운 계단 수 - Dynamic Programming / Java • 문제 링크 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net • 풀이 과정 dp 배열을 2차원 배열로 정의하였으며, 이는 dp[자릿수][자릿값] 을 의미한 graycode.tistory.com 위 문제와 유사하게 2차원 dp 배열로 접근하여 풀이한다. 이친수.. 2022. 8. 24. [백준] 10844 쉬운 계단 수 - Dynamic Programming / Java • 문제 링크 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net • 풀이 과정 dp 배열을 2차원 배열로 정의하였으며, 이는 dp[자릿수][자릿값] 을 의미한다. 이때 오버플로우를 방지하기 위하여 long 형으로 정의한다. 이때 각 자릿값의 계단수를 구하는 코드는 dp[i - 1][j - 1] + dp[i - 1][j + 1] 이며, 예시로 dp[3][4] 이 주어질 때, 위의 코드를 적용하면 dp[2][3], dp[2][5] 가 구해지게 된다. dp[3][4] - - 4 dp[2][3] - 3 4 dp[2][5] - 5 4 다만 자릿값이 0 일 경우 다음 자릿수의 값은 1 만 가능하고, 자릿값이 9 일 경우 다음 자릿수의 값.. 2022. 8. 23. [백준] 1389 케빈 베이컨의 6단계 법칙 - Graph Theory / Java • 문제 링크 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net • 풀이 과정 [백준] 11404 플로이드 - Graph Theory / Java • 문제 링크 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 graycode.tistory.com 위 문제와 유사한 구조의 Floyd-Warshall 알고리즘 문제이다. 모든 노드간.. 2022. 8. 22. [백준] 11404 플로이드 - Graph Theory / Java • 문제 링크 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net • 풀이 과정 모든 노드간 최단 경로를 구하는 Floyd-Warshall 알고리즘을 활용한다. 2차원 배열에 자기 자신 노드로 이동하는 경우을 제외한 모든 최단 거리를 inf 값으로 지정하고, 이때 inf 값을 Integer.MAX_VALUE 로 지정 시 오버플로우가 발생할 수 있으므로 정점과 간선의 최대값의 곱에 1을 더한 수로 지정하였다. 이 후 간선의 정보를 입력받는데 같은 간선이 추가로 주어질 시 가중치의 최소값을 매번 갱신하여, dist 배.. 2022. 8. 21. 이전 1 ··· 181 182 183 184 185 186 187 ··· 203 다음
