[PS] 백준 #19949. 영재의 시험

Algorithms/PS

[PS] 백준 #19949. 영재의 시험

퐁키조아 2022. 1. 17. 10:59

문제 정보

난이도: 실버 III
문제 주소: https://www.acmicpc.net/problem/19949
이 문제를 푼 이유: 그룹 연습 Div 2

문제

컴퓨터공학과 학생인 영재는 이번 학기에 알고리즘 수업을 수강한다.

평소에 자신의 실력을 맹신한 영재는 시험 전날까지 공부를 하지 않았다.

당연하게도 문제를 하나도 풀지 못하였지만 다행히도 문제가 5지 선다의 객관식 10문제였다.

찍기에도 자신 있던 영재는 3개의 연속된 문제의 답은 같지 않게 한다는 자신의 비법을 이용하여 모든 문제를 찍었다.

이때 영재의 점수가 5점 이상일 경우의 수를 구하여라.

문제의 점수는 1문제당 1점씩이다.

나의 풀이

이 문제는 표본 공간을 탐색하다가 특정 조건을 만족하면 컷오프를 하는 형태로 만들어야겠다고 생각했다. grading 함수는 현재 문제번호, 이전에 선택한 번호, 이전에 선택한 번호가 누적된 횟수, 이전 문제까지의 점수를 매개변수로 갖는다.

종료 조건은 문제 번호가 10을 초과했을때로 총 점수가 5점 이상이면 cnt를 1 증가시킨 후 종료한다. 또 다른 종료조건은 코드를 짜다가 추가했는데 현재 score와 남은 문제의 개수의 합이 5보다 작으면 절대 5점 이상이 나올 수 없으므로 컷오프를 하도록 만들어주었다. 초기 함수는 grading(1, 0, 1, 0) 이다. (이전에 선택한 번호는 없음)

grading 함수는 각 번호마다 (1~5) 현재 이전 번호와 누적된 상태인지 / 선택한 번호가 정답인지에 따라서 grading 함수를 다르게 호출한다. 모두 공통적으로 문제 번호는 1 증가시킨다.

[누적 횟수 3 미만, 이전 번호와 같은 번호, 정답인 경우] 누적 횟수 +1, score +1
[누적 횟수 3 미만, 이전 번호와 다른 번호, 오답인 경우] 누적 횟수 +1, score +0
[누적 횟수 3 이상이거나 이전 번호와 다른 번호, 정답인 경우] 누적 횟수 1로 초기화, score +1
[누적 횟수 3 이상이거나 이전 번호와 다른 번호, 오답인 경우] 누적 횟수 1로 초기화, score +0

처음 코드를 짰을 때는 예제의 답이 자꾸 145324가 출력되었다. 어디가 문제일까 하고 로직을 따라가보니 if (score >= 5) 이면 바로 cnt++ 하고 바로 return 을 하게 한 것이 문제였다. 뒤의 모든 경우를 무시하고 score가 5 이상이면 컷오프가 되었기 때문이였다. 그래서 probNum이 10을 초과했는지를 먼저 검사하게 수정하니 정답을 출력하였다.

#include <bits/stdc++.h>
using namespace std;

int ans[11];
int cnt = 0;

// 145324?

// 문제번호, 이전에 선택한 번호, 누적횟수, 점수
void grading(int probNum, int pastNum, int stack, int score) {
	// cout << probNum << "번 / 이전 선택: " << pastNum << " / 누적: " << stack << ", " << score << endl;
	if (probNum > 10) {
		if (score >= 5) cnt++; 
		return;
	}
	if (score + (11 - probNum) < 5) return;

	for (int i = 1; i <= 5; i++) {
		if (stack < 2 && i == pastNum) { // 누적 + 중복될 경우 스택 증가
			if (i == ans[probNum]) grading(probNum + 1, i, stack + 1, score + 1);
			else grading(probNum + 1, i, stack + 1, score);
		}
		else { // 누적 or 다른 걸로 변경
			if (i != pastNum) {
				if (i == ans[probNum]) grading(probNum + 1, i, 1, score + 1);
				else grading(probNum + 1, i, 1, score);
			}
		}
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	for (int i = 1; i <= 10; i++) cin >> ans[i];
	grading(1, 0, 1, 0);
	cout << cnt;
}

저작자표시