Cute Running Puppy
본문 바로가기
728x90

개발일기89

[백준] 계단 오르기 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씩 늘리면서 비교하여 풀었다. 1 2 3 4 5 6 7 ( 6, 13 ) 0 0 0 0 0 13 13 ( 4, 8 ) ( 3, 6 ) ( 5, 12 ) 물건 1 = (무게 : 6, 가치 : 13) 물건 1개로 짐을 싸는 방법 무게가 6부터 담을 수 있으므로 6과 7에 13만큼의 가치를 담을 수 있다. 1 2 3 4 5 6 7 ( 6, 13 ) 0 0 0 0 0 13 13 ( 4 , 8 ) 0 0 0 8 8 max( 8 + 0 , 13) = 13 max( 8 + 0 , 13) = 13 (3, 6) (5, 12) 물건 1 = (무게 : 6, 가치 : 13) 물건 2 = (무게 : 4, .. 2023. 7. 16.
[백준] 1, 2, 3 더하기 - 자바 DP는 왜 이렇게 어려운지... 날 울린다...* 근데 식이 보이면 이렇게 허무할 수 없다.... 흥 1, 2, 3의 합은 각각 1 (1 가지) 1 2 (2 가지) 1 + 1 2 3 (4 가지) 1 + 1 + 1 1 + 2 2 + 1 3 4는 1, 2, 3씩 뺀 수와 표현할 수 있다.(1, 2, 3으로만 표현하기 위해) 즉, 3 + 1, 2 + 2, 1 + 3으로 표현할 수 있다. 3 (4 가지) + 1 1 + 1 + 1 + 1 1 + 2 + 1 2 + 1 + 1 3 + 1 2 (2 가지) + 2 1 + 1 + 2 2 + 2 1 (1 가지) + 3 1 + 3 즉 4를 표현하는 방식은 4 (4 + 2 + 1 = 7 가지) 1 + 1 + 1 + 1 1 + 2 + 1 2 + 1 + 1 3 + 1 1 + 1 +.. 2023. 7. 16.
728x90

티스토리툴바