[백준/C++] 알고리즘 2961번 - 도영이가 만든 맛있는 음식

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 2961번 - 도영이가 만든 맛있는 음식을 풀어보도록 하겠습니다.

 

 

https://www.acmicpc.net/problem/2961

2961번: 도영이가 만든 맛있는 음식

 

[문제 접근]

시간제한 1초이고, n은 10이하이기 때문에 완전탐색이 가능하다고 생각했습니다. 각 재료마다 포함여부를 고려하여 백트래킹으로 접근했습니다. 이후 비트마스킹 풀이도 가능하다고 판단하여 비트마스킹으로도 풀어보았습니다.

 

[풀이 전략]

백트래킹

1. 백트래킹 함수를 생성합니다.

- 인자는 depth, 신맛의 총곱, 쓴맛의 총합으로 합니다.

- base condition은 depth 가 n일때 함수를 종료합니다.

- 현재 재료를 포함하면 backTracking(depth+1, totS*s[depth], totB*b[depth]) 호출 

- 현재 재료를 포함하지 않으면 backTracking(depth+1, totS,totB) 호출

2. 백트래킹 함수 호출합니다.

 

비트마스킹

1. 최소 재료 한 가지 조건과 더불어 재료의 모든 경우를 돌기 위해  for문을 1부터 1<<n( 2^n)까지 확인합니다.

2. totS =1, totB = 0 으로 생성 및 초기화합니다.

3. 재료비트가 1인 경우에만  각 재료의 비트를 돌면서 totS와 totB를 업데이트해줍니다.

4. 3번이 끝나고 totS와 totB의 차이가 answer에 있는 값과 비교하여 작으면 업데이트 해줍니다.

 

[코드]

백트래킹

#include <iostream>
#include <algorithm>
using namespace std;


int n ;
int s[11] ;
int b[11] ; 

int answer = 1e9; 

void backTracking(int depth, int totS, int totB){
    if(depth == n) return;
        answer = min(answer, abs(totS*s[depth] - totB-b[depth]));
        backTracking(depth+1,totS*s[depth],totB+b[depth]);
        backTracking(depth+1, totS,totB);
}

int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n ;
    
    for(int i = 0 ; i < n ; i++){
        cin >> s[i] >> b[i] ;
    }

    backTracking(0,1,0);
    cout << answer ; 
}

 

비트마스킹

#include <iostream>
#include <algorithm>
using namespace std;


int n ;
int s[11] ;
int b[11] ; 

int answer = 1e9; 


int main() {
      ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n ;
    for(int i = 0 ; i < n ; i++){
        cin >> s[i] >> b[i] ;
    }

    for(int tmp = 1 ; tmp < (1 << n) ; tmp++){
        int totS = 1 ; int totB = 0;
        for(int j = 0 ; j < n ; j++){
            if((tmp & (1 << j)) == 0) continue;
            totS *= s[j];
            totB += b[j];
        }
        answer = min(answer,abs(totS - totB));
    }

    cout << answer ; 
}

 

[배울 점]

- 백트래킹에서 최소 하나라는 조건을 고려하는 게 조금 어려웠는데 이럴 때는 비트마스킹이 더 직관적임을 기억.