문제
제출 코드(JAVA)
코드 제출
class Solution {
public int solution(int[] money) {
int answer = 0;
int length = money.length;
int[] dp =new int[length-1];
int[] dp2= new int[length];
dp[0]=money[0];
dp[1]=money[0];
dp2[0]=0;
dp2[1]=money[1];
for(int i=2;i<length-1;i++){
dp[i]=Math.max(dp[i-2]+money[i],dp[i-1]);
}
for(int i=2;i<length;i++){
dp2[i]=Math.max(dp2[i-2]+money[i],dp2[i-1]);
}
return Math.max(dp[length-2],dp2[length-1]);
}
}첫번째 집부터 시작 || 두번째 집부터 시작의 경우의 수를 두고, 순회하면서 최대값으로 업데이트하는게 관건.
정확성 테스트
정확성 테스트
테스트 1 〉 통과 (0.08ms, 51.8MB)
테스트 2 〉 통과 (0.17ms, 53.4MB)
테스트 3 〉 통과 (0.12ms, 52.1MB)
테스트 4 〉 통과 (0.07ms, 51.7MB)
테스트 5 〉 통과 (0.08ms, 52.3MB)
테스트 6 〉 통과 (0.12ms, 52.2MB)
테스트 7 〉 통과 (0.11ms, 52.5MB)
테스트 8 〉 통과 (0.08ms, 51.7MB)
테스트 9 〉 통과 (0.17ms, 52.6MB)
테스트 10 〉 통과 (0.08ms, 52.4MB)
효율성 테스트
테스트 1 〉 통과 (22.65ms, 103MB)
테스트 2 〉 통과 (22.56ms, 102MB)
테스트 3 〉 통과 (22.27ms, 103MB)
테스트 4 〉 통과 (22.31ms, 102MB)
테스트 5 〉 통과 (24.31ms, 100MB)
테스트 6 〉 통과 (39.67ms, 102MB)
테스트 7 〉 통과 (20.47ms, 89.4MB)
테스트 8 〉 통과 (20.03ms, 76.3MB)
테스트 9 〉 통과 (25.45ms, 94MB)
테스트 10 〉 통과 (24.87ms, 102MB)제출 코드(Python)
첫번째 코드 제출
def solution(money):
dp = [0 for i in range(len(money)-1)]
dp2 = [0 for i in range(len(money))]
dp[0] = dp[1] = money[0]
dp2[0] = 0
dp2[1] = money[1]
for i in range(2, len(money)-1):
dp[i] = max(dp[i-2]+money[i], dp[i-1])
for i in range(2, len(money)):
dp2[i] = max(dp2[i-2]+money[i], dp2[i-1])
return max(dp[len(money)-2], dp2[len(money)-1])Java와 같은 풀이 방식이나 상당한 시간이 소요되는 것을 확인할 수 있다.
정확성 테스트
정확성 테스트
테스트 1 〉 통과 (0.33ms, 10.2MB)
테스트 2 〉 통과 (0.96ms, 10.4MB)
테스트 3 〉 통과 (0.69ms, 10.1MB)
테스트 4 〉 통과 (0.05ms, 10.3MB)
테스트 5 〉 통과 (0.27ms, 10.1MB)
테스트 6 〉 통과 (0.61ms, 10.2MB)
테스트 7 〉 통과 (0.41ms, 10.2MB)
테스트 8 〉 통과 (0.31ms, 10.3MB)
테스트 9 〉 통과 (0.95ms, 10.2MB)
테스트 10 〉 통과 (0.20ms, 10.3MB)
효율성 테스트
테스트 1 〉 통과 (579.07ms, 96.2MB)
테스트 2 〉 통과 (529.27ms, 90.8MB)
테스트 3 〉 통과 (560.78ms, 94.1MB)
테스트 4 〉 통과 (627.89ms, 94.8MB)
테스트 5 〉 통과 (496.31ms, 78.8MB)
테스트 6 〉 통과 (534.41ms, 91.4MB)
테스트 7 〉 통과 (325.00ms, 57.3MB)
테스트 8 〉 통과 (321.17ms, 58.7MB)
테스트 9 〉 통과 (396.46ms, 66.8MB)
테스트 10 〉 통과 (570.53ms, 92.4MB)두번째 코드 제출
def solution(a):
x1, y1, z1 = a[0], a[0], a[0]+a[2]
x2, y2, z2 = 0, a[1], a[2]
for i in a[3:]:
x1, y1, z1 = y1, z1, max(x1, y1)+i
x2, y2, z2 = y2, z2, max(x2, y2)+i
return max(x1, y1, y2, z2)파이썬의 장점을 살린 간결한 코드.
이중 for문을 줄여 성능 개선이 된 것을 확인
정확성 테스트
정확성 테스트
테스트 1 〉 통과 (0.20ms, 10.2MB)
테스트 2 〉 통과 (0.35ms, 10.2MB)
테스트 3 〉 통과 (0.20ms, 10.2MB)
테스트 4 〉 통과 (0.03ms, 10.2MB)
테스트 5 〉 통과 (0.15ms, 10.3MB)
테스트 6 〉 통과 (0.33ms, 10.4MB)
테스트 7 〉 통과 (0.23ms, 10.1MB)
테스트 8 〉 통과 (0.17ms, 10.2MB)
테스트 9 〉 통과 (0.53ms, 10.2MB)
테스트 10 〉 통과 (0.13ms, 10.2MB)
효율성 테스트
테스트 1 〉 통과 (301.01ms, 45.3MB)
테스트 2 〉 통과 (285.17ms, 42.9MB)
테스트 3 〉 통과 (341.15ms, 44.2MB)
테스트 4 〉 통과 (344.76ms, 44.6MB)
테스트 5 〉 통과 (276.50ms, 38.6MB)
테스트 6 〉 통과 (287.34ms, 43.1MB)
테스트 7 〉 통과 (180.35ms, 29.4MB)
테스트 8 〉 통과 (181.51ms, 29.9MB)
테스트 9 〉 통과 (211.41ms, 33.4MB)
테스트 10 〉 통과 (303.71ms, 43.3MB)
Be More!