Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 2357
- 트리
- 에라토스테네스의 체
- 모던 JavaScript 튜토리얼
- 정수론
- 애드 혹
- 맵
- 슬라이딩 윈도우
- 플로이드-워셜
- 문자열
- 해시 테이블
- boj
- 구현
- JavaScript
- 투 포인터
- 그래프
- BFS
- 정렬
- 13164
- 이분 탐색
- SSAFY
- Python
- DP
- 브루트포스
- 세그먼트 트리
- 싸피
- 수학
- 누적 합
- 그리디
- DFS
Archives
- Today
- Total
흙금이네 블로그
[BOJ] 15658 - 연산자 끼워넣기 (2) (Python, JavaScript) 본문
아이디어
DFS로 주어진 연산자로 가능한 식을 만들어 그 최댓값과 최솟값을 찾는다.
풀이 #1 (Python)
덧셈, 뺄셈, 곱셈, 나눗셈을 수행하는 람다식들을 리스트 cal에 저장한다.
리스트 operator에 각 연산자의 개수를 저장하고, 최댓값과 최솟값을 저장하는 리스트 res를 생성한다.
함수 dfs에서는 재귀 호출로 주어진 연산자를 사용하여 식을 만들고, 식을 모두 만들면 결과값과 비교하여 갱신해 나간다.
cal = [lambda a, b: a+b, lambda a, b: a-b, lambda a, b: a*b, lambda a, b: a//b if a > 0 else -(-a//b)]
def dfs(idx, total, a, s, m, d):
global res
if idx >= N:
if total > res[0]:
res[0] = total
if total < res[1]:
res[1] = total
return
if a > 0:
dfs(idx+1, cal[0](total, A[idx]), a-1, s, m, d)
if s > 0:
dfs(idx+1, cal[1](total, A[idx]), a, s-1, m, d)
if m > 0:
dfs(idx+1, cal[2](total, A[idx]), a, s, m-1, d)
if d > 0:
dfs(idx+1, cal[3](total, A[idx]), a, s, m, d-1)
N = int(input())
A = list(map(int, input().split()))
operator = list(map(int, input().split()))
res = [-int(1e10), int(1e10)]
dfs(1, A[0], *operator)
print(res[0])
print(res[1])
풀이 #2 (JavaScript)
풀이 #1과 같은 방식으로 동작한다.
나눗셈 결과를 parseInt 함수를 사용하여 정수 형태로 처리하며, res의 최댓값과 최솟값을 -Infinity와 Infinity로 초기화한다.
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
function dfs(idx, total, a, s, m, d) {
if (idx >= N) {
if (total > res[0]) res[0] = total;
if (total < res[1]) res[1] = total;
return;
}
if (a > 0) dfs(idx+1, total+A[idx], a-1, s, m, d);
if (s > 0) dfs(idx+1, total-A[idx], a, s-1, m, d);
if (m > 0) dfs(idx+1, total*A[idx], a, s, m-1, d);
if (d > 0) dfs(idx+1, parseInt(total/A[idx]), a, s, m, d-1);
}
const N = Number(input[0]);
const A = input[1].split(' ').map(Number);
const operator = input[2].split(' ');
let res = [-Infinity, Infinity];
dfs(1, A[0], ...operator);
console.log(`${res[0]}`);
console.log(`${res[1]}`);
자바스크립트에서는 -0과 0이 구분되는데, 이 문제에서 계산 결과로 나오는 -0을 잘 처리하지 않아 많이 틀렸다.
템플릿 문자열과 parseInt 함수를 이용하여 -0을 출력하면 0이 출력된다.
그러나 parseInt 함수에 -0을 인자로 직접 넘기지 않고 -0이 나오는 계산식을 인자로 넘기면 -0이 출력된다.
`${-0}`; // 0
parseInt(-0); // 0
parseInt(-1/2); // -0
parseInt(1/-2); // -0
-0과 0은 구분되지만 서로 비교 연산을 수행하면 참이 나온다.
console.log(-0 === 0); // true
'알고리즘' 카테고리의 다른 글
[BOJ] 14712 - 넴모넴모 (Easy) (Python, JavaScript) (0) | 2023.02.08 |
---|---|
[BOJ] 2631 - 줄세우기 (Python) (0) | 2023.02.08 |
[BOJ] 2011 - 암호코드 (Python) (0) | 2023.02.07 |
[BOJ] 18429 - 근손실 (Python, JavaScript) (0) | 2023.02.06 |
[BOJ] 2096 - 내려가기 (Python) (0) | 2023.02.05 |
Comments