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
- 에라토스테네스의 체
- 이분 탐색
- 구현
- 싸피
- Python
- 애드 혹
- 투 포인터
- 맵
- BFS
- JavaScript
- 문자열
- 슬라이딩 윈도우
- DP
- SSAFY
- 트리
- 플로이드-워셜
- 정수론
- 정렬
- DFS
- 세그먼트 트리
- 수학
- 13164
- 브루트포스
- 그리디
- 해시 테이블
- 2357
- 모던 JavaScript 튜토리얼
- 누적 합
- boj
- 그래프
Archives
- Today
- Total
흙금이네 블로그
[BOJ] 3980 - 선발 명단 (Python, JavaScript) 본문
아이디어
DFS과 백트래킹으로 남은 포지션에 선수들을 채워 나가며 능력치 합의 최댓값을 찾는다.
풀이 #1 (Python)
각각의 테스트 케이스에 대해 선수들의 능력치를 리스트 S에 입력 받는다.
메모리 절약과 DFS에서 빠른 접근을 위해 능력치가 0이 아닌 선수들만 인덱스와 능력치를 추가해 나간다.
포지션 할당 표시를 위해 0으로 채워진 리스트 visited를 생성하고 함수 dfs를 호출한다.
함수 dfs에서는 차례로 i 번째 선수를 적합한 포지션 중 남은 포지션에 배치하여 할당 표시 후,
현재 선수의 능력치 a를 능력치 합 total에 더하여 다음 선수로 함수를 재귀 호출한다.
배치가 끝나면 결과값 res와 능력치 합 total을 비교해 결과값을 능력치 합의 최댓값으로 갱신해 나간다.
import sys
input = sys.stdin.readline
def dfs(i, total):
global res
if i < 11:
for j, a in S[i]:
if visited[j] == 0:
visited[j] = 1
dfs(i+1, total+a)
visited[j] = 0
elif total > res:
res = total
C = int(input())
for c in range(C):
S = []
for i in range(11):
S.append([])
temp = list(map(int, input().split()))
for j in range(11):
if temp[j]:
S[-1].append((j, temp[j]))
res = 0
visited = [0]*11
dfs(0, 0)
print(res)
풀이 #2 (JavaScript)
풀이 #1과 같은 방식으로 동작한다.
선수들 능력치 배열 S, 결과값 저장 변수 res, 포지션 할당 표시 배열 visited를 for문 밖에서 선언한다.
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
function dfs(i, total) {
if (i < 11) {
for (let [j, a] of S[i]) {
if (visited[j] == 0) {
visited[j] = 1;
dfs(i+1, total+a);
visited[j] = 0;
}
}
}
else if (total > res) res = total;
}
const C = Number(input[0]);
let S, res, visited;
for (let c=0; c<C; c++) {
S = [];
for (let i=0; i<11; i++) {
S.push([])
temp = input[c*11+i+1].split(' ').map(Number);
for (let j=0; j<11; j++) {
if (temp[j]) S[i].push([j, temp[j]])
}
}
res = 0;
visited = Array(11).fill(0);
dfs(0, 0);
console.log(res);
}
'알고리즘' 카테고리의 다른 글
[BOJ] 2661 - 좋은수열 (Python, JavaScript) (0) | 2023.02.10 |
---|---|
[BOJ] 15681 - 트리와 쿼리 (Python) (0) | 2023.02.10 |
[BOJ] 1509 - 팰린드롬 분할 (Python) (0) | 2023.02.09 |
[BOJ] 14712 - 넴모넴모 (Easy) (Python, JavaScript) (0) | 2023.02.08 |
[BOJ] 2631 - 줄세우기 (Python) (0) | 2023.02.08 |
Comments