글 읽기 - 알고리즘 지적해주시면 감사합니다!

sochun1518 2년 전 0

[알고리즘설명]

1) 브루트포스하게 (a,b) 쌍을 모두 순회하며 가능한 (a,b) 쌍을 찾습니다.

2) 가능한 (a,b) 쌍을 이용해 다음 숫자를 만들고 (list[N - 1] * a + b)

다음 숫자가 값이 같으면 의미가 없으므로 자료구조 Map을 이용해서 값이 다른 다음 숫자들을 모두 모아줍니다.

3) 다음 숫자가 여러개라면 A, 없다면 B, 하나라면 하나를 출력해줍니다.

게시판 반례 및 정답 코드를 봐도 어디가 문제인지 발견을 못했습니다...!

N개의 숫자가 절대값이 100보다 작으므로 (a, b) 쌍이 -100 ~ 100 이면 충분할 것 같은데

넉넉히 -500 ~ 500으로 줘도 시간이 넉넉해서 그렇게 설정해줬습니다.

#include<iostream>
#include<map>

using namespace std;

bool checkNum(int N, int list[50], int a, int b){
	for (int k = 0; k < N - 1; k++)
		if (list[k] * a + b != list[k + 1])
			return false;
	return true;
}

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

	int N, list[50] = {};

	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> list[i];

	map<int, int> nextNums;

	for (int a = -500; a <= 500; a++) {
		for (int b = -500; b <= 500; b++) {
			int nextNum = list[N - 1] * a + b;
			if (checkNum(N, list, a, b) && nextNums.find(nextNum) == nextNums.end()) // (a,b) 가 정답이고 만들어지는 다음 숫자가 없을 때
				nextNums.insert({ list[N - 1] * a + b, 1 });
		}
	}

	if (nextNums.empty()) cout << "B\n";
	else if (nextNums.size() >= 2) cout << "A\n";
	else cout << nextNums.begin()->first << '\n';

	return 0;
}

djs100201 2년 전 1

3
10 9 -91

ans:-10091

out:B

sochun1518 2년 전 0

ㅏ....너무감사드립니다...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

알고리즘 지적해주시면 감사합니다!

sochun1518 2년 전 0

djs100201 2년 전 1

sochun1518 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말