kokoball의 devlog
article thumbnail
728x90

1. 문제

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

2. 문제 해석

이 문제는 입력 제한부터 완전탐색의 냄새가 났다. (1 <= N <= 19)

관건은 재귀 조건이였는데 문제에 힌트가 있었다.

 

자세히 봐야하는 조건은 중첩된 괄호는 사용할 수 없다인데 이 조건으로 인해 계산시 고려해야 하는 부분은 지금 계산하고 있는 부분과 그 다음 부분까지만 고려하면 되었다.

 

이를 현재 위치와 남은 길이를 비교하여 새로운 재귀 조건을 추가해 주었다.

 

3. 풀이

<bash />
const filePath = process.platform === "linux" ? "dev/stdin" : "../test.txt"; const input = require("fs").readFileSync(filePath).toString().trim().split("\n"); const calc = (oper, a, b) => { if (oper === "+") { return a + b; } else if (oper === "-") { return a - b; } else { return a * b; } }; function solution(input) { const N = input[0].split().map(Number)[0]; const arr = input[1].split(""); let ans = -Infinity; let nums = []; let opers = []; for (let i = 0; i < N; i++) { if (i % 2 === 0) { nums.push(Number(arr[i])); } else { opers.push(arr[i]); } } nums = nums.map((num) => Number(num)); const check = (here, number) => { console.log(here, number, -1); if (here === nums.length - 1) { ans = Math.max(ans, number); return; } check(here + 1, calc(opers[here], number, nums[here + 1])); if (here + 2 <= nums.length - 1) { const temp = calc(opers[here + 1], nums[here + 1], nums[here + 2]); check(here + 2, calc(opers[here], number, temp)); } }; check(0, nums[0]); return ans; } console.log(solution(input));

 

 

728x90
profile

kokoball의 devlog

@kokoball-dev

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!