백준 2287번(모노디지털 표현)

jh Seo·2023년 2월 28일
백준한번에 못 푼 문제해시
0

백준

목록 보기
132/180

개요

백준 2287번: 모노디지털 표현

  • 입력
    첫째 줄에 K가 주어진다. 다음 줄에는 표현 식을 찾을 수의 개수 n(1 ≤ n ≤ 1,000)이 주어진다. 다음 줄에는 K-표현 중 가장 짧은 길이를 알아보려 하는 자연수 a(1 ≤ a ≤ 32,000)가 주어진다.

  • 출력
    입력되는 순서대로 K-표현의 최소 길이를 n개의 줄에 출력한다. 만약 K-표현의 최소 길이가 8보다 크다면 “NO"를 출력한다.

접근 방식

처음 접근방식(틀린 방식)

  1. 처음에 딱 보고 느꼇던 생각은 괄호처리가 까다롭다고 느꼈다.
    따라서 괄호를 신경쓰지 않기 위해 연산자 우선순위를 무시하고
    수식의 앞에서부터 차례대로 계산하는 식으로 구현하였다.

  2. K를 kAmount개를 사용했을 때, 각 K사이에 모든 부호를 하나씩 다 넣는 브루트 포스 방식으로 구현을 하였다.
    (어차피 최대 K가 8개이므로 5^7개의 연산을 하게되는데 크기가 크지않아서 가능할것이라고 생각했다.)

  3. 각 K사이에 부호를 넣거나 부호를 안넣고 K를 그냥 붙이는 방식으로 두자리수 세자리수를 구현하였고, 총 수식은 string형으로
    저장 후 Calculate함수를 통해 string수식을 계산하여 결과를 반환하였다.

  4. 하지만 예제코드도 통과하고 몇가지 테스트를 해봐도 다 통과하던 코드지만 정작 accept를 못 받았다. 며칠간 고민하고 여기저기 검색하고 물어본 결과 앞에서부터 차례대로 연산하는 과정이 잘못된 것이였다. 예를들어 7로 50을 만들면 7*7+7/7이렇게 4개로 가능하지만 내 Calculate함수는 (7*7+7)*7 이렇게 계산을 해서 7 4개로 50을 만들수가 없던 것이였다.

두 번째 방식

  1. 따라서 set을 이용한 방식으로 풀었다.
    크기가 9인 set배열을 만들고, 각 배열의 인덱스에는
    해당 인덱스 갯수의 K로 만들 수 있는 모든 경우의 수를
    저장해준다.

  2. 만들 수 있는 경우의 수는 기본적으로 바텀업 방식으로
    i개의 K로 만들 수 있는 수는,
    1개로 만들 수 있는 모든 수와 i-1개로 만들 수 있는 모든 수의 조합,
    2개로 만들 수 있는 모든 수와 i-2개로 만들 수 있는 모든 수의 조합,
    이런식으로 표현 될 수 있고, 1개부터 이제 만들 수 있는 모든 수가 set에 저장 되므로 다시 안 구하고 바로 사용할 수 있다.

  3. 기본적으로 kAmount개의 K로 만들 수 있는 수의 set에는
    kAMount개의 K를 이어 붙힌 수를 저장 후,
    1개의 k로 만들 수 있는 수와 kAmount-1개의 K로 만들 수 있는 수의 모든 연산 결과를 저장,
    2개의 k로 만들 수 있는 수와 kAmount-2개의 K로 만들 수 있는 수의 모든 연산 결과를 저장,
    이렇게 쭉쭉 저장해갔다.

    //kAmount개의 K로 만들 수 있는 모든 수를 Cal[kAMount]에 저장
bool CanMake(int kAmount, int target) {
	//kAmount개의 K를 이어붙여서 저장할 변수
	int tmp = 0;
	for (int i = 0; i < kAmount; i++) {
		tmp = tmp * 10 + K;
	}
	//tmp저장하고
	Cal[kAmount].insert(tmp);
	//-tmp도 저장한다
	Cal[kAmount].insert(-tmp);
	//kAMount까지
	for (int i = 1; i < kAmount; i++) {
		//Cal[i]에 저장된 모든 값과
		for (int A : Cal[i]) {
			//Cal[kAMount-i]에 저장된 모든값을 연산해서 저장
			for (int B : Cal[kAmount - i]) {
				if (i <= kAmount / 2) {
					Cal[kAmount].insert(A + B);
					Cal[kAmount].insert(A - B);
					Cal[kAmount].insert(A * B);
				}
				//DivisionByZero오류 범하지 않기위해 B가 0이 아닐때만
				if (B) Cal[kAmount].insert(A / B);

			}
		}

	}

세번째 방식

첫번째 방식 코드의 짜임새에 맞춰 변형하려니 두번째방식에서
테스트케이스마다 새로 연산하게 되었다.
따라서 K값을 받자마자 1개의 K부터 8개의 K까지 만들 수 있는 모든 수를 미리 구해서 저장한 후, 테스트케이스마다 해당 수가
set에 있는지 체크해서 답을 내도록 개조하였다.

첫번째 방식 코드(string형으로 수식을 만들어 푸는 방식 - 틀림)

#include<iostream>
#include<string>

using namespace std;
int K, N;
char symbol[4] = { '+' , '-' , '/' , '*' };

// string형을 받아서 해당 문자열을 계산해서 결과를 반환하는 함수
int Calculate(const string& ans) {
	//계산이 이미끝난 좌항
	int result = 0;
	//계산을 해야할 우항
	int currentNum = 0;
	//입력받을 부호
	char currentOp = '+';

	for (char c : ans) {
		//숫자면 currentNum에 넣고
		if (isdigit(c)) {
			currentNum = currentNum * 10 + (c - '0');
		}
		//부호면 계산 
		else {
			switch (currentOp) {
			case '+': result += currentNum; break;

			case '-':
				if (currentNum >= result) result = currentNum - result;
				else result -= currentNum;
				break;
			case '*': result *= currentNum; break;
			case '/':
				result /= currentNum;
				break;
			}
			currentOp = c;
			currentNum = 0;
		}
	}
	switch (currentOp) {
	case '+': result += currentNum; break;
	case '-':
		if (currentNum >= result) result = currentNum - result;
		else result -= currentNum; break;
	case '*': result *= currentNum; break;
	case '/':
		result /= currentNum;
		break;
	}

	return result;
}

/// <summary>
/// k를 kAMount개 사용했을때 나올수 있는 값중에 target값이 나올 수 있는지 조사하는 함수
/// offset은 string ans에 숫자나 부호 넣을 오프셋 위치
/// </summary>
/// <param name="ans(계산식)"></param>
/// <param name="kAmount(K의 갯수)"></param>
/// <param name="offset(부호넣을 공간)"></param>
/// <param name="target(만들어야하는 숫자)"></param>
/// <returns>kAmount개 만으로 target값이 만들어지면 true아니면 false</returns>
bool CanMake(string ans, int kAmount, int offset, int target) {
	bool ret = false;
	if (offset == kAmount - 1)
	{
		if (kAmount == 1) {
			return ans.back() - '0' == target;
		}
		if (Calculate(ans) == target)
			return true;
		else
			return false;
	}
	for (int i = 0; i < 5; i++) {
		//이전 i번째 심볼넣었을때 target값 만들수 있다면 빠져나옴
		if (ret) return ret;
		//4일땐 부호없을 때으 케이스로 자릿수 하나 키우는 의미로 숫자 그냥 붙여줌
		if (i == 4) ret = CanMake(ans + ans.back(), kAmount, offset + 1, target);
		else {
			string tmp = ans + symbol[i];
			ret = CanMake(tmp + ans.back(), kAmount, offset + 1, target);
		}
	}
	return ret;
}

void Solution(int input) {
	//if target number can be made by i amount of K, print i out to console
	for (int i = 1; i <= 8; i++) {
		if (CanMake(to_string(K), i, 0, input)) {
			cout << i << '\n';
			return;
		}
	}
	//else print No
	cout << "No" << '\n';
}

void Input() {
	int input = 0;
	cin >> K >> N;
	for (int i = 0; i < N; i++) {
		cin >> input;
		Solution(input);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();

}

두 번째 방식 코드(통과하지만 비효율적)

#include<iostream>
#include<string>
#include<set>

using namespace std;
int K, N;
//1개부터 8개의 K로 만들 수 있는 모든 수 저장용 set
set<int> Cal[9];

//kAmount개의 K로 만들 수 있는 모든 수를 Cal[kAMount]에 저장
bool CanMake(int kAmount, int target) {
	//kAmount개의 K를 이어붙여서 저장할 변수
	int tmp = 0;
	for (int i = 0; i < kAmount; i++) {
		tmp = tmp * 10 + K;
	}
	//tmp저장하고
	Cal[kAmount].insert(tmp);
	//-tmp도 저장한다
	Cal[kAmount].insert(-tmp);
	//kAMount까지
	for (int i = 1; i < kAmount; i++) {
		//Cal[i]에 저장된 모든 값과
		for (int A : Cal[i]) {
			//Cal[kAMount-i]에 저장된 모든값을 연산해서 저장
			for (int B : Cal[kAmount - i]) {
				if (i <= kAmount / 2) {
					Cal[kAmount].insert(A + B);
					Cal[kAmount].insert(A - B);
					Cal[kAmount].insert(A * B);
				}
				//DivisionByZero오류 범하지 않기위해 B가 0이 아닐때만
				if (B) Cal[kAmount].insert(A / B);

			}
		}

	}
	//연산이 끝난 후 Cal[kAMount]의 모든 원소중에 target이 있다면 return true;
	for (int elem : Cal[kAmount]) {
		if (elem == target)
			return true;
	}

	return false;
}

void Solution(int input) {
	//if target number can be made by i amount of K, print i out to console
	for (int i = 1; i <= 8; i++) {
		if (CanMake(i, input)) {
			cout << i << '\n';
			return;
		}
	}
	//else print No
	cout << "NO" << '\n';
}

void Input() {
	int input = 0;
	cin >> K >> N;
	for (int i = 0; i < N; i++) {
		cin >> input;
		Solution(input);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();

}

세번째 방식(위 방식보다 효율적)

#include<iostream>
#include<string>
#include<set>

using namespace std;
int K, N;
//1개부터 8개의 K로 만들 수 있는 모든 수 저장용 set
set<int> Cal[9];

//kAmount개의 K로 만들 수 있는 모든 수를 Cal[kAMount]에 저장
void MakeSet(int kAmount) {
	//kAmount개의 K를 이어붙여서 저장할 변수
	int tmp = 0;
	for (int i = 0; i < kAmount; i++) {
		tmp = tmp * 10 + K;
	}
	//tmp저장하고
	Cal[kAmount].insert(tmp);
	//-tmp도 저장한다
	Cal[kAmount].insert(-tmp);
	//kAMount까지
	for (int i = 1; i < kAmount; i++) {
		//Cal[i]에 저장된 모든 값과
		for (int A : Cal[i]) {
			//Cal[kAMount-i]에 저장된 모든값을 연산해서 저장
			for (int B : Cal[kAmount - i]) {
				if (i <= kAmount / 2) {
					Cal[kAmount].insert(A + B);
					Cal[kAmount].insert(A - B);
					Cal[kAmount].insert(A * B);
				}
				//DivisionByZero오류 범하지 않기위해 B가 0이 아닐때만
				if (B) Cal[kAmount].insert(A / B);

			}
		}

	}
}
//Cal[1]부터 Cal[8]내에 input이 있는지 찾아서 있다면 i값 없다면 NO출력
void Solution(int input) {
	int i = 1;
	for (i; i<9&&Cal[i].find(input) == Cal[i].end(); i++) { }
	if(i==9)cout << "NO" << '\n';
	else cout << i << '\n';
}

void Input() {
	int input = 0;
	cin >> K >> N;
	//1개의 K부터 8개의 K로 만들 수 있는 모든 수 다 Cal에 저장
	for (int i = 1; i <= 8; i++) {
		MakeSet(i);
	}
	//그 후 값 받을때마다 찾아서 출력
	for (int i = 0; i < N; i++) {
		cin >> input;
		Solution(input);
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();

}

문풀후생

첫번째 방식이 무조건 된다는 집념에 사로잡혀서
왜 틀렸는지 반례를 찾다가 시간을 너무 낭비했다.
내가 찾지도못했고 인터넷에서 찾았지만 그래도 찾아서 다행이라고 생각한다.
또 이런 계산기를 구현할진 모르겠지만 그때 확실히 기억할 수 있을 것 같다.

profile
jh Seo
코딩 창고!
이전 포스트

백준 1351(무한 수열)

다음 포스트

백준 11279(최대 힙)

0개의 댓글