BOJ 9806번 문제 정보
- 해결 일자 : 2023년 7월 1일
- solved.ac 난이도 : Bronze III (해결일 기준)
BOJ 9806번 문제 번역 (영어)
옛날 어느 나라에 큰 왕국을 가진 왕이 살고 있었습니다. 그는 매우 영리한 왕이었지만 한 가지 약점이 있었습니다. 그는 세 개까지만 셀 수 있다는 것이었습니다.
그런데 그는 이것이 정말 큰 결점이라고 생각하지 않았습니다. 그에게는 100까지 셀 수 있는 마법사가 많았기 때문입니다. 그리고 그들 중 일부는 심지어 천까지 말하기도 했습니다. 그래서 괜찮았습니다. 그러나 어느 날 수적으로 많은 야만인이 사방에서 접근하기 시작하면서 왕국에 슬픔이 찾아왔습니다. 그리고 왕은 인생에서 가장 중요한 결정을 내려야 했습니다. 그는 군대를 이끌기 위해 국경으로 보낼 장군을 만들기 위해 아들 중 누군가를 선택해야 했습니다.
그러나 왕은 그의 아들 중 일부는 자신처럼 영리하지만, 일부는 상당히 어리석어 잘못된 결정으로 군대의 사기를 떨어뜨릴 수 있다는 것을 알고 있었습니다. 더 정확하게는, 그는 자기의 아들들 각각의 정신적 잠재력, 즉 -3에서 3까지의 정수(왕은 최대 3까지만 셀 수 있다는 점을 기억하십시오)에 대해 알고 있었습니다. 그는 또한 그의 군대가 야만인을 물리칠 확률이 그가 장군으로 만들 아들들의 정신 잠재력의 일부 힘의 합에 비례한다는 것을 알고 있었습니다(힘 지수는 양의 정수로 그의 모든 아들에게 동일하고 3개를 초과하지 않습니다). 따라서 그는 자기의 아들들을 이끌어갈 조합을 선택해야 했습니다.
군대는 이 금액이 최대한 가능할 것이라고 말했습니다.
그러나 왕 자신은 모든 적절한 계산을 할 수 없었습니다. 예를 들어 3을 초과하지 않는 수(그 제곱)의 두 번째 거듭제곱은 3보다 클 수 있었기 때문에 그는 가장 똑똑한 마법사인 당신에게 이 문제를 해결하라고 요청했습니다.
입력 형식
입력 파일의 첫 번째 줄에는 왕의 아들 수(100 이하의 정수)가 포함됩니다. 두 번째 줄에는 야만인을 물리칠 확률을 계산하는 데 사용되는 공식의 지수인 3을 초과하지 않는 양의 정수가 포함되어 있습니다. 세 번째 줄에는 왕의 아들들의 정신 잠재력 목록이 포함되어 있습니다. 모든 정수는 절댓값이 3보다 크지 않습니다.
출력 형식
설명된 합계로 측정된 야만인을 물리칠 수 있는 최대 확률을 출력하세요.
BOJ 9806번 문제 풀이
왕의 각 아들에 대하여 잠재력의 일정 제곱의 값이 양수이면 그 값을 더하고, 음수 또는 0이면 무시하면 됩니다. 지수의 값은 3 이하이고, 모든 잠재력의 절댓값이 3 이하이므로 반복문을 사용해도 무방합니다.
BOJ 9806번 소스 코드
#include <bits/stdc++.h>
using namespace std;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int N, P;
cin >> N >> P;
int answer = 0;
for (int i = 0; i < N; i++) {
int M;
cin >> M;
int X = 1;
for (int p = 0; p < P; p++) X *= M;
if (X > 0) answer += X;
}
cout << answer << endl;
}