16637 괄호 추가하기
+, -, *로 이루어진 수식이 주어진다.
항상 올바른 수식이 주어지며,
숫자도 1~9까지의 정수가 주어진다.
올바르게 괄호를 쳐서 최대값을 만들어라.
단
- 중첩된 괄호는 사용할 수 없다.
- 왼쪽에서부터 계산한다.
가령 3+8×7-9×2의 경우
(3+8)×7-9×2의 수식으로 바꿀 수 있으며,
(3+8)×7-9×2
11×7-9×2
77-9×2
68*2
136
136이 된다.(77-9×2에서 × 연산자가 아닌 77-9가 먼저 계산되는 점이 실제 사칙 연산과 다르다.)
풀이
- 현실과 다른 부분이 있으니 문제를 꼼꼼히 읽어야 한다.
- 사칙연산 문제라는 점, 그리고 '연산자의 우선 순위는 같으며 왼쪽부터 계산된다'는 부분에서 스택 문제임을 알 수 있다.
- 스택 문제이지만 '연산자의 우선순위가 같다'는 점에서 결국 완전탐색을 해야한다.
- 스택 + 완전탐색...? => DFS로 풀이할 수 있다.
DFS를 설계해보자.
'왼쪽에서 부터 계산'한다는 점에서 착안하여,
DFS 함수 :
현재까지 계산한 값을 DFS에 넘겨준다. (prevValue)
괄호로 묶어 계산을 한 다음 칸에는 당연히 연산자가 나올 것이다.(ope)
그리고 현재까지 계산한 값을 다시 탐색할 필요가 없으므로, 어디서부터 계산해야 하는지를 넘겨준다. (현재위치 + 1(ope의 위치) + 1(다음 숫자의 위치))
종료조건 :
-
괄호로 묶지 않으면 종료된다고 본다. 이 경우 answer를 최대 값으로 갱신한다.
-
괄호로 묶지 못할 때에도 종료된다. 괄호로 묶이는 조건은 '숫자, 문자, 숫자'이다. 만일 다음 숫자의 위치 인덱스와 전체 문자열 길이의 차이가 3 미만이면 더 이상 괄호로 묶을 일이 없으므로 재귀 호출을 하지 않는다.
그 밖에 '값이 음수가 되면 점점 안 좋아 지는건가?' 등의 종료 조건을 생각해볼 수 있으나, -(1-9)와 같이 -(음수)는 +가 된다. 결과적으로 이러한 조건들도 탐색하기 위해 전체 탐색을 진행해야 한다. -
괄호가 0개일 때
8*3+5+2answer = 31 -
괄호가 1개일 때 (괄호가 끝나는 지점까지의 연산결과와 괄호 직후의 연산자, 괄호 직후의 연산자 이후의 포인터를 넘긴다.) recur(prevValue, ope, currentPointer)
(8*3)+5+2recur(24, "+", 2+2)
answer = Math.max(answer, 24+4)8*(3+5)+2(문자열 길이 - currentPointer)가 3 미만이므로 재귀 x
answer = Math.max(answer, 64+6)8*3+(5+2)- (문자열 길이 - currentPointer)가 3 미만이므로 재귀 x
answer = Math.max(answer, 64+6)
- 괄호가 2개일 때
1-1)(8*3)+(5+2)(문자열 길이 - currentPointer)가 3 미만이므로 재귀 x)
answer = Math.max(answer, 24+4)
여기서 또 한가지 구현 포인트는... 어떻게 현재까지를 연산해서 넘겨줄까이다.
고민하다가 answer = Math.max(answer, 24+4) 부부븐을 마지막에 넘겨주고,
'괄호로 다음을 묶은 다음 재귀 호출하기' 혹은 '현재까지만 계산하고 재귀 호출하기'의 두 가지 선택이 있음을 알고 아래와 같이 수정한다.
1-1) 8*3+5+2 recur(8, *, 2)
1-2) (8*3)+5+2 recur(24, +, 4)
1-1-1) 8*3+5+2 recur(24, +, 4)
1-1-2) 8*(3+5)+2 recur(64, +, 6)
1-2-1) (8*3)+5+2 recur(29, +, 6)
1-2-2) (8*3)+(5+2) answer = Math.max(answer, 31)
1-1-1-1) 8*3+5+2 answer = Math.max(answer, 31)
1-1-2-1) 8*(3+5)+2 answer = Math.max(answer, 66)
1-2-1)...
...
모두 다 괄호로 묶어 pointer === n이 되었을 때 종료하는 방식이다.
여기서 또 고민... 중복된 계산이 너무 많이 나온다.
그래서 set()을 이용해서 중복된 계산을 피하려고도 해봤는데, 연산 속도에서는 차이가 없었다.
중복된 계산이 '+' 연산자에서만 나오고, '-'나 '*'는 괄호에 따른 연산 순서에 따라 값이 달라지므로, 더 이상 최적화가 불가능하다.
단, 최적화를 할 수 있는 방법이 있는데, + 연산자끼리는 괄호를 묶지 않는 것이다. 최적화 성능은....별로 차이가 없긴 하다.
코드
const fs = require("fs");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
let inputArray = fs
.readFileSync(filePath)
.toString()
.trim() //인풋 마지막 개행을 삭제
.split("\n")
.map((e) => e.trim()); //로컬 환경에서 \r을 삭제
const n = inputArray[0];
const input = inputArray[1];
console.log(solution(n, input)); // 주어진 수식을 계산하여 결과값을 반환하는 함수를 호출하고, 결과값을 출력한다.
function solution(n, s) {
// 수식의 길이와 수식 문자열을 인자로 받는 함수를 정의한다.
let answer = -1 * Number.MAX_SAFE_INTEGER; // 계산 결과 중 최대값을 저장할 변수를 초기화한다.
function myOperator(num1, oper, num2) {
// 두 개의 숫자와 연산자를 받아 계산 결과를 반환하는 함수를 정의한다.
if (oper === "+") {
return num1 + num2;
}
if (oper === "-") {
return num1 - num2;
}
if (oper === "*") {
return num1 * num2;
}
}
function dfs(index, value) {
// 현재 인덱스와 계산 결과값을 인자로 받아 괄호를 추가하여 모든 계산식을 탐색하는 함수를 정의한다.
if (index == n - 1) {
// 수식의 끝까지 도달한 경우
answer = Math.max(answer, value); // 현재까지 계산한 결과값과 이전까지의 최대값을 비교하여 더 큰 값을 answer에 저장한다.
return;
}
if (index + 2 < n) {
// 괄호로 묶을 수 있는 경우
dfs(index + 2, myOperator(value, s[index + 1], parseInt(s[index + 2]))); // 현재까지 계산한 결과값과 다음 연산자와 다음 숫자를 계산하여 재귀 호출한다.
}
if (index + 4 < n) {
// 이번엔 건너뛰고 그 다음을 괄호로 묶을 수 있는 경우
dfs(
index + 4,
myOperator(
value,
s[index + 1],
myOperator(
parseInt(s[index + 2]),
s[index + 3],
parseInt(s[index + 4])
)
)
); // 현재까지 계산한 결과값과 다음 연산자와 두 개의 숫자를 계산하여 재귀 호출한다.
}
}
dfs(0, parseInt(s[0])); // 인덱스 0과 첫 번째 숫자를 인자로하여 dfs 함수를 호출한다.
return answer; //정답을 반환
}
17070 파이프 옮기기 1
백준
단순 구현 문제이다.
- 모든 값을 탐색해야 한다.
- 하지만 '최단 경로'가 아닌 '가능한 모든 경로'를 계산하므로 BFS가 아닌 DFS이다.
- 특정 지점 [i][j]로 오는 경로가 이전 경로의 영향을 받으면서 진행되므로 부모와 자식이 독립이 아니다. 따라서 DP가 아닌 DFS이다.
- 사실 이 문제는 DP로도 풀 수 있다. DP 테이블을 '[i][j]로 오는 모든 경우의 수'로 하면 된다. 하지만 설정된 공간 복잡도와 문제의 특성을 보아 DFS를 의도한 문제로 보인다.
이 문제의 특이한 점은 마지막 지점에 도착하지 못하는 경우에는 시간 초과가 난다는 점이다.
일반적인 상황은 아니고, 문제에서 BFS를 못하게 막는 제약을 거는 과정에서 FOR문이 중첩되지 못하도록 시간 제약을 걸어두었기 때문에 발생하는 문제 같다. (목적지에서부터 거슬러 출발 지점으로 오거나, 양방향 BFS 등으로 풀 수도 있겠으나 문제의 의도는 아닌 것 같다.)
예외 처리만 해주고 패스하는 걸로..
//////* 인풋을 입력받는 코드입니다. *//////
const fs = require("fs");
const filePath =
process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
let [n, ...input] = fs
.readFileSync(filePath)
.toString()
.trim() //인풋 마지막 개행을 삭제
.split("\n");
input = input.map((e) => e.split(" ").map((e) => ~~e));
console.log(solution(n, input));
function solution(n, mtx) {
let answer = 0;
const start = [0, 1];
// const vectors = [
// [1, 0],
// [0, 1],
// [1, 1],
// ];
const dfs = (position, direction) => {
if (position[0] === n - 1 && position[1] === n - 1) return (answer += 1);
for (let i = 0; i < 3; i++) {
if (i === 0) {
if (
direction !== "h" &&
mtx[position[0] + 1] &&
!mtx[position[0] + 1][position[1]]
) {
dfs([position[0] + 1, position[1]], "v");
}
} else if (i === 1) {
if (
direction !== "v" &&
position[1] + 1 < n &&
!mtx[position[0]][position[1] + 1]
) {
dfs([position[0], position[1] + 1], "h");
}
} else if (i === 2) {
if (
mtx[position[0] + 1] &&
position[1] + 1 < n &&
!mtx[position[0]][position[1] + 1] &&
!mtx[position[0] + 1][position[1]] &&
!mtx[position[0] + 1][position[1] + 1]
) {
dfs([position[0] + 1, position[1] + 1], "d");
}
}
}
};
if (!mtx[n - 1][n - 1]) {
dfs(start, "h");
}
return answer; //정답을 반환
}
17135 캐슬 디펜스
n, m의 매트릭스가 주어진다.
사정거리 d가 주어진다.
- 성 안에 궁수를 3명 배치한다.
- 사정거리안에 있는 적 중 가장 가까운 적을 쏜다.
- 가장 가까운 적이 여럿인 경우 왼쪽 적부터 쏜다.
- 매 턴마다 적군이 성으로 다가온다.
- 한 번의 배치로 최대 몇 마리를 쏠 수 있는지 구하라.
격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.
풀이
먼저 완전탐색으로 풀 수 있을 것이다.
성 안에 3명의 궁수를 배치하는 경우의 수는 O(n^3)이다. 여기에 적군을 몇 명이나 쏠 수 있는지를 구하다보면.... ㅎㄷㄷ
동기의 팁 성의 한 변이 3에서 15까지이다. O(n^3)으로 풀어도 풀이가 가능하므로 시뮬레이션 문제이다.
문제를 재해석한다.
- 적군이 성으로 다가온다고 생각하지 말고 궁수가 한 칸씩 앞으로 나아간다고 생각한다. (사정거리가 1씩 증가+매트릭스의 가장 아랫줄이 00000...이 된다고 해도 무방하다. 격자판에서의 거리는 칸 수로 계산되니까.)
- 가까운 적은 '왼쪽'부터 쏜다. 즉
7
638
52149
순으로 순회한다.
풀이 참조
다른 사람들은 2번의 과정을 벡터로 풀이하였다.
1번의 과정은 배열을 통째로 교체해주는 방식으로 풀이하였다.