728x90 개발일기/알고리즘12 [백준] 제곱수의 합 - 자바 1개로 표현할 수 있는 이 수를 생각하면서! 풀면 된다. 2²보다 작은 수 1²으로만 표현할 수 있다. 따라서 2²보다 크고 3²보다 작은 수 1²과 2²으로 표현할 수 있다. 이것을 1²과 2²으로 시작하는 수로 표현한다면 4일 때 이것을 앞의 수와 비교해보면 이렇게 표현할 수 있다. 따라서 더 적은 항의 수를 택하여 이렇게 표현할 수 있다. 5일 때 1²과 2²으로 시작하는 수로 표현한다면 이것을 앞의 수와 비교해보면 이렇게 표현할 수 있다. 6, 7, 8일 때 따라서 2²보다크고 3²보다 작은 수는 다음과 같이 표현할 수 있다. 3²보다 크고 4²보다 작은 수 1²과 2²과 3²으로 표현할 수 있다. 9일 때 이것을 1²과 2²과 3²으로 시작하는 수로 표현한다면 이것을 앞의 수와 비교해보면 이렇게.. 2023. 7. 24. [백준] 쉬운 계단 수 - 자바 N = 1일 때 '0으로 시작하는 수는 계단수가 아니다.' 라는 조건으로 인해 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 끝나는 수 0 1 2 3 4 5 6 7 8 9 N=1 0 1 1 1 1 1 1 1 1 1 N = 2일 때 0은 1에서 올 수 있음 dp[2][0] = dp[1][1] → dp[i][j] = dp[i-1][1] (0에서 시작은 안 되지만 중간에 낄 수 있음) 끝나는 수 0 1 2 3 4 5 6 7 8 9 N=1 0 1 1 1 1 1 1 1 1 1 N=2 1 9는 8에서 올 수 있음 dp[2][9] = dp[1][8] → dp[i][j] = dp[i-1][8] (다음 칸이 없으므로 내려오는 경우는 불가) 끝나는 수 0 1 2 3 4 5 6 7 8 9 N=1 0 1 1 1 1 1 .. 2023. 7. 22. [백준] 계단 오르기 vs 포도주 시식 - 자바 ✔️ 계단 오르기 규칙 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 우선 계단의 점수와 현재 도착한 방법 중 최대값을 저장할 변수를 선언한다. int[] dp = new int[N+1]; int[] stair = new int[N+1]; 첫 번째 계단은 첫 번째 계단에 도착했을 때 최대값을 가짐 dp[1] = stair[1] 두 번째 계단은 첫번째 계단에서 올랐을 때 최대값을 가짐 dp[2] = stair[1] + stair[2]; 세 번째 계단은 첫 번째, 두 번째 계단 중 더 .. 2023. 7. 22. [백준] 2×n 타일링 - 자바 비교적 쉽게 풀은 ! 그려보다 보면 눈에 잘 보인다! i = 2이기 위해 i = 0에서 + 2를 해야하므로 두개를 가로로 쌓고 (세로로 쌓으면 겹치는 방법이 존재) i = 1에서 + 1을 해야하므로 세로로 하나를 쌓는다. i = 3이기 위해 i = 1에서 + 2를 해야하므로 두개씩 가로로 쌓고 (세로로 쌓으면 겹치는 방법이 존재) i = 2에서 + 1을 해야하므로 세로로 하나씩 쌓는다. i = 4이기 위해 i = 2에서 + 2를 해야하므로 두개씩 가로로 쌓고 (세로로 쌓으면 겹치는 방법이 존재) i = 3에서 + 1을 해야하므로 세로로 하나씩 쌓는다. i = 5이기 위해 i = 3에서 + 2를 해야하므로 두개씩 가로로 쌓고 (세로로 쌓으면 겹치는 방법이 존재) i = 4에서 + 1을 해야하므로 세로로 하.. 2023. 7. 17. 이전 1 2 3 다음 728x90
