7199 : 백트래킹 종합 1
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
두 가지 백트래킹 문제를 복합적으로 수행하는 종합 계산기입니다.
- T = 1: 전구 스위치 문제의 최소 조작 횟수 계산 (7194)
- T = 2: 배낭 문제의 최대 가치 합 계산 (7198)
[제약 조건]
• 입력되는 모든 수는 정수입니다.
- T = 1: 전구 스위치 문제의 최소 조작 횟수 계산 (7194)
- T = 2: 배낭 문제의 최대 가치 합 계산 (7198)
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 유형 T가 주어집니다.
- T = 1인 경우, 둘째 줄에 N, M이 주어지고 셋째 줄에 전구 초기 상태, 넷째 줄부터 M개의 줄에 스위치 제어 목록이 주어집니다.
- T = 2인 경우, 둘째 줄에 N, W가 주어지고 셋째 줄부터 N개의 줄에 각 물건의 무게와 가치가 주어집니다.
- T = 1인 경우, 둘째 줄에 N, M이 주어지고 셋째 줄에 전구 초기 상태, 넷째 줄부터 M개의 줄에 스위치 제어 목록이 주어집니다.
- T = 2인 경우, 둘째 줄에 N, W가 주어지고 셋째 줄부터 N개의 줄에 각 물건의 무게와 가치가 주어집니다.
출력 설명
유형에 따른 백트래킹 탐색 결과를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
1
3 2
0 0 0
1 2
2 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
-1도움
T=1이고 해당 전구 상태와 스위치 정보에서는 -1이 정답입니다.