[ BOJ / C++ ] 2961번 도영이가 만든 맛있는 음식
9471 단어 브루트포스brute forcebojcppboj
이번 문제는 브루트포스 알고리즘을 활용하여 해결하는 문제였다.
- n을 입력받고 n만큼 s와 b를 입력받는다.
- ts에 s를 모두 곱한 값을 저장하고, tb에 b를 모두 더한 값을 저장한다.
- 사용 여부를 체크하기 위한 bool형 used배열을 사용하여 모든 경우를 확인한다.
- 확인할 때는 ts에서 s를 나누고, tb에서 b를 빼며 확인한다.
Code
#include <iostream>
#include <vector>
#include <math.h>
#define MAX 11
using namespace std;
int n;
long long sb[MAX][MAX];
bool used[MAX];
long long ts=1, tb=0;
long long result=0;;
void Input(){
cin>>n;
for(int i=0; i<n; i++){
cin>>sb[i][0]>>sb[i][1];
ts*=sb[i][0];
tb+=sb[i][1];
}
result=abs(ts-tb);
}
void Solution(int n, long long s, long long b){
if(n==0){
return;
}
if(result>abs(s-b)){
result=abs(s-b);
}
for(int i=0; i<n; i++){
if(!used[i]){
used[i]=true;
Solution(n-1, s/sb[i][0], b-sb[i][1]);
used[i]=false;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Input();
Solution(n, ts, tb);
cout<<result<<endl;
return 0;
}
#include <iostream>
#include <vector>
#include <math.h>
#define MAX 11
using namespace std;
int n;
long long sb[MAX][MAX];
bool used[MAX];
long long ts=1, tb=0;
long long result=0;;
void Input(){
cin>>n;
for(int i=0; i<n; i++){
cin>>sb[i][0]>>sb[i][1];
ts*=sb[i][0];
tb+=sb[i][1];
}
result=abs(ts-tb);
}
void Solution(int n, long long s, long long b){
if(n==0){
return;
}
if(result>abs(s-b)){
result=abs(s-b);
}
for(int i=0; i<n; i++){
if(!used[i]){
used[i]=true;
Solution(n-1, s/sb[i][0], b-sb[i][1]);
used[i]=false;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
Input();
Solution(n, ts, tb);
cout<<result<<endl;
return 0;
}
Author And Source
이 문제에 관하여([ BOJ / C++ ] 2961번 도영이가 만든 맛있는 음식), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xx0hn/BOJ-C-2961번-도영이가-만든-맛있는-음식저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)