💡문제
N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다.
i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있다.
- 에너지 구슬 하나를 고른다. 고른 에너지 구슬의 번호를 x라고 한다. 단, 첫 번째와 마지막 에너지 구슬은 고를 수 없다.
- x번째 에너지 구슬을 제거한다.
- Wx-1 × Wx+1의 에너지를 모을 수 있다.
- N을 1 감소시키고, 에너지 구슬을 1번부터 N번까지로 다시 번호를 매긴다. 번호는 첫 구슬이 1번, 다음 구슬이 2번, ... 과 같이 매겨야 한다.
N과 에너지 구슬의 무게가 주어졌을 때, 모을 수 있는 에너지 양의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 에너지 구슬의 개수 N(3 ≤ N ≤ 10)이 주어진다.
둘째 줄에는 에너지 구슬의 무게 W1, W2, ..., WN을 공백으로 구분해 주어진다. (1 ≤ Wi ≤ 1,000)
출력
첫째 줄에 모을 수 있는 에너지의 최댓값을 출력한다.
예제입력
4
1 2 3 4예제출력
12📖내가 실패한 Code
import sys
"""
첫번째 마지막 에너지 구슬 못고름. 에너지 구슬 하나 고름 그걸 x
x번째 제거
wx-1xw+1 모을 수 있음
n을 1 감소시키고 다시 번호 매김. 최대 에너지 값을 매김
-> n이 10개 뿐임
1초임
그냥 전체 돌려도 될듯
N =2가 될 때 까지 돌리면 끝
같은 맥스 에너지일 경우는 없어지는게 더 작으면 그만
"""
def find_max_energy(n, array):
max_index, max_energy = 1, 1
for i in range(1, n-1):
if max_energy < (energy := array[i-1] * array[i+1]):
max_index = i
max_energy = energy
elif max_energy == energy and array[max_index] > array[i]:
max_index = i
max_energy = energy
return max_index, max_energy
def main():
n, *array = map(int, sys.stdin.read().split())
answer = 0
while n > 2:
max_index, max_energy = find_max_energy(n, array)
array.pop(max_index)
answer += max_energy
n -= 1
sys.stdout.write(str(answer))
if __name__ == "__main__":
main()
📖내가 작성한 Code
import sys
"""
첫번째 마지막 에너지 구슬 못고름. 에너지 구슬 하나 고름 그걸 x
x번째 제거
wx-1xw+1 모을 수 있음
n을 1 감소시키고 다시 번호 매김. 최대 에너지 값을 매김
-> n이 10개 뿐임
1초임
그냥 전체 돌려도 될듯
N =2가 될 때 까지 돌리면 끝
같은 맥스 에너지일 경우는 없어지는게 더 작으면 그만
-> 틀림
재귀적 구성으로 전체를 다 파악해야함
"""
answer = 0
def find_max_energy(n, array, sum_energy):
global answer
if n == 2:
answer = max(answer, sum_energy)
return
for i in range(1, n-1):
find_max_energy(n-1, array[:i]+array[i+1:], sum_energy+array[i-1]*array[i+1])
def main():
n, *array = map(int, sys.stdin.read().split())
find_max_energy(n, array, 0)
sys.stdout.write(str(answer))
if __name__ == "__main__":
main()
✍️풀이과정
최근에 코딩 테스트를 2가지 쳤다. 그런데 실버들을 틀리는 어처구니 없는 실수를 저질렀다. 이유는 최근에 랜덤하게 풀지 않았고 시간을 정하고 풀지 않아서 인 것 같다. 따라서, 실버들을 생각 10분 구현 30분으로 하는 문제들을 풀어볼 생각이다.
이것도 처음에 틀려버렸다. 재귀로 구성해야한다는 것을 생각하지 못했다. 유사 문제들을 풀어봐야 감이 잡힌다고 한다.
그래서, 재귀적으로 구성하고 통과.
🧠 코드 리뷰
- 전역 변수 사용
- 문제점: 전역 변수 answer를 사용하면 함수 간의 의존성이 생기고, 디버깅이나 테스트 시 예기치 않은 부작용이 발생할 수 있습니다.
- 개선: 재귀 함수가 최대 에너지 값을 반환하도록 구현하여, 전역 변수 대신 반환값을 이용합니다.
- 재귀 호출과 불필요한 리스트 복사
- 문제점: 매 재귀 호출마다 array[:i] + array[i+1:]로 리스트를 복사하는 것은 n이 작아서 큰 문제는 아니지만, 코드의 가독성을 떨어뜨릴 수 있습니다.
- 개선: 문제 크기가 작으므로 큰 성능 문제는 없지만, 함수 내부에서 리스트 복사가 어떻게 이루어지는지 명시적으로 설명해주면 좋습니다.
- 함수명 및 인자 명 명료성
- 문제점: 함수 이름 find_max_energy는 탐색 로직이 재귀적임을 충분히 표현하지 않습니다.
- 개선: dfs나 search_max_energy 같은 이름으로 변경해 재귀 탐색임을 암시하는 것이 좋습니다.
- 입출력 처리
- 문제점: sys.stdin.read().split()과 sys.stdout.write() 사용은 문제 풀이에서는 괜찮지만, 가독성 측면에서는 일반적인 input()과 print()를 사용하는 것도 고려해볼 수 있습니다.
- 개선: 백준 온라인 저지에서는 빠른 입출력이 필요할 수 있으므로 이 방식도 유지할 수 있습니다.
5.코드 주석
- 문제점: 주석이 코드와 혼용되어 있어, 코드의 의도와 로직을 이해하는 데 도움이 되지만, 주석 내용이 수정 전과 후를 구분하지 않으면 혼란을 줄 수 있습니다.
- 개선: 주석을 최신 로직에 맞게 정리하고, 각 함수의 역할과 인자, 반환값에 대해 명시해주는 것이 좋습니다.
🛠️AI 개선 코드
import sys
def dfs(beads, current_energy):
"""
beads: 현재 에너지 구슬 리스트
current_energy: 지금까지 누적된 에너지 값
반환: 해당 구슬 순서에서 얻을 수 있는 최대 총 에너지 값
"""
# 구슬이 두 개만 남으면 더 이상 제거할 수 없음
if len(beads) == 2:
return current_energy
max_energy = 0
# 첫 번째와 마지막 구슬은 제거할 수 없으므로 1부터 len(beads)-2까지
for i in range(1, len(beads)-1):
# i번째 구슬을 제거했을 때 추가되는 에너지
added_energy = beads[i-1] * beads[i+1]
# 새로운 구슬 배열 생성 (i번째 제거)
new_beads = beads[:i] + beads[i+1:]
# 재귀 호출하여 최대 에너지 계산
total_energy = dfs(new_beads, current_energy + added_energy)
max_energy = max(max_energy, total_energy)
return max_energy
def main():
input_data = sys.stdin.read().split()
n = int(input_data[0])
beads = list(map(int, input_data[1:]))
result = dfs(beads, 0)
sys.stdout.write(str(result))
if __name__ == "__main__":
main()
💻결과
🖱️참고 링크
우물 안에서 무언가 만드는 사람