[BOJ#16198] 에너지 모으기 (Python, NodeJS)

https://www.acmicpc.net/problem/16198

1 초

512 MB

5969

4478

3599

76.041%

문제

N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다.

i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있다.

1. 에너지 구슬 하나를 고른다. 고른 에너지 구슬의 번호를 x라고 한다. 단, 첫 번째와 마지막 에너지 구슬은 고를 수 없다.
2. x번째 에너지 구슬을 제거한다.
3. Wx-1 × Wx+1의 에너지를 모을 수 있다.
4. N을 1 감소시키고, 에너지 구슬을 1번부터 N번까지로 다시 번호를 매긴다. 번호는 첫 구슬이 1번, 다음 구슬이 2번, ... 과 같이 매겨야 한다.

N과 에너지 구슬의 무게가 주어졌을 때, 모을 수 있는 에너지 양의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 에너지 구슬의 개수 N(3 ≤ N ≤ 10)이 주어진다.

둘째 줄에는 에너지 구슬의 무게 W1, W2, ..., WN을 공백으로 구분해 주어진다. (1 ≤ Wi ≤ 1,000)

출력

첫째 줄에 모을 수 있는 에너지의 최댓값을 출력한다.

---

제출코드 (Python)

N = int(input())
energy = list(map(int, input().split()))

def charge(energy, cur):    
    if len(energy) == 2:
        return cur
        
    max_val = 0
    for i in range(1, len(energy)-1):
        sumone = energy[i-1] * energy[i+1]
        new_val = energy[:i] + energy[(i+1):]
        max_val = max(max_val, charge(new_val, cur + sumone))
    
    return max_val

print(charge(energy, 0))

기존의 N과 M에서 사용했던 코드에서 배열 자체를 들고다니는 코드로 작성했다.

리턴되는 값인 max_val이 cur + sumone 으로 계속 갱신되도록 해서 값을 받았는데 생각보다 가독성이 떨어지는것 같다..

 

제출코드(NodeJs)

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = parseInt(input[0])
const energy = input[1].split(' ').map(Number)

let ans = 0

function charge(energy, cur) {
  if (energy.length === 2) {
    ans = Math.max(ans, cur)
    return
  }

  for (let i = 1; i < energy.length - 1; i++) {
    let sumone = energy[i - 1] * energy[i + 1]
    let new_val = energy.splice(i, 1)[0]
    charge(energy, cur + sumone)
    energy.splice(i, 0, new_val)
  }
}

charge(energy, 0)
console.log(ans)

최근 도전해보고 있는 Node 로 알고리즘 풀기.

js로 백트래킹은 처음이라 여러가지 검색으로 도움을 받았다.

fs모듈을 호출해서 입력값을 받고 파이썬과 같은 로직이지만,

pop과 insert를 splice 하나로 처리할 수 있다는 점은 편리한 것 같다.