[ 백준 ] 2961 도영이가 만든 맛있는 음식 - JavaScript

2025. 4. 3. 23:34·알고리즘
목차
  1. 문제
  2. 입력
  3. 출력
  4. 입출력 예시
  5. 풀이

문제

도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.

 

지금 도영이의 앞에는 재료가 N개 있다. 도영이는 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.

 

시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이는 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.

 

재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

 

입력

첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다.

출력

첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다.

 

입출력 예시

입력

4
1 7
2 6
3 8
4 9

 

출력

1

 

 

 


 

 

풀이

'use strict';
const fs = require('fs');

// 백준 제출 할 때 주석 제거
// const readFileSyncAddress = '/dev/stdin';

// VSC 테스트 할 때 주석 제거
const readFileSyncAddress = 'input.txt';

const input = fs.readFileSync(readFileSyncAddress).toString().trim().split('\n');
const N = Number(input.shift());

const element = [];
input.forEach(flavor => {
  element.push(flavor.split(' ').map(Number));
});

let diff = 1000000000;

const graph = Array.from({ length: N }, () => []);

for (let i = 1; i < N; i++) {
  for (let j = i; j < N; j++) {
    graph[i - 1].push(j);
  }
}

function updateDiff(sour, bitter) {
  const tempDiff = Math.abs(sour - bitter);
  if (tempDiff < diff) diff = tempDiff;
}

function dfs(v, sour, bitter) {
  updateDiff(sour, bitter);
  if (graph[v].length === 0) return;

  for (let node of graph[v]) {
    dfs(node, sour * element[node][0], bitter + element[node][1]);
  }
}

element.forEach((flavor, index) => dfs(index, flavor[0], flavor[1]));

console.log(diff);

 

신맛과 쓴맛의 차이가 가장 적은 조합을 찾으려면, 모든 조합을 직접 계산해보는 수밖에 없습니다.

 

즉, 이 문제는 완전탐색으로 풀어야 합니다. 저는 이 조합을 구하기 위해 DFS(깊이 우선 탐색) 를 활용했습니다.

 

제 아이디어는 먼저 1을 시작으로 모든 경우의 수를 탐색하는 그래프 구조를 만드는 것이었습니다.

 

1을 선택한 상태에서 나올 수 있는 모든 조합을 탐색한 뒤, 그다음에는 2를 시작으로 하는 조합을,

또 그다음에는 3, 4... 이런 식으로 각 재료를 시작점으로 하여 가능한 모든 조합을 탐색하려는 구조였습니다.

 

이렇게 하면 각 재료를 선택한 경우부터 시작해서 만들 수 있는 모든 경우의 수를 순차적으로 완전 탐색할 수 있다고 생각했습니다.

 

 

1. graph 배열을 이용해 트리 형태 구성

const graph = Array.from({ length: N }, () => []);
for (let i = 1; i < N; i++) {
  for (let j = i; j < N; j++) {
    graph[i - 1].push(j);
  }
}

사진처럼, 각 노드(재료 번호)에서 자기보다 큰 인덱스를 자식으로 연결해서 트리 형태의 조합 그래프를 만들었습니다.

 

2. 각 재료를 시작점으로 DFS 수행

element.forEach((flavor, index) => dfs(index, flavor[0], flavor[1]));

각 재료를 한 번씩 시작 노드로 삼아 해당 재료를 포함한 조합을 모두 탐색합니다.

 

3. DFS로 신맛 * 곱셈, 쓴맛 + 덧셈 누적하며 차이 갱신

function dfs(v, sour, bitter) {
  updateDiff(sour, bitter);
  if (graph[v].length === 0) return;

  for (let node of graph[v]) {
    dfs(node, sour * element[node][0], bitter + element[node][1]);
  }
}

재귀적으로 다음 재료를 선택하면서 신맛은 곱하고, 쓴맛은 더해가며 모든 가능한 조합을 탐색합니다.

'알고리즘' 카테고리의 다른 글

[ 백준 ] 1325 효율적인 해킹 - JavaScript  (0) 2025.04.09
[ 백준 ] 2512 예산 - JavaScript  (0) 2025.04.04
[ 백준 ] 1260 DFS와 BFS - JavaScript  (0) 2025.03.31
[ 프로그래머스 ] 단속카메라 - JavaScript  (0) 2025.03.31
[ 백준 ] 11660 구간 합 구하기 5 - JavaScript  (0) 2025.03.31
  1. 문제
  2. 입력
  3. 출력
  4. 입출력 예시
  5. 풀이
'알고리즘' 카테고리의 다른 글
  • [ 백준 ] 1325 효율적인 해킹 - JavaScript
  • [ 백준 ] 2512 예산 - JavaScript
  • [ 백준 ] 1260 DFS와 BFS - JavaScript
  • [ 프로그래머스 ] 단속카메라 - JavaScript
seio924
seio924
seio924 님의 블로그 입니다.
  • seio924
    seio924 님의 블로그
    seio924
  • 전체
    오늘
    어제
    • ROOT (51)
      • Mark Up (1)
      • Style Sheet (1)
      • Language (5)
        • JavaScript (5)
      • CS (0)
      • 알고리즘 (26)
      • 디자인 패턴 (1)
      • Develop (8)
      • 디자인 툴 (1)
      • COCOMU (8)
      • FRIENDY (0)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    figma
    백준
    디스코드 봇 제작
    react
    cocomu
    알고리즘
    Pretendard
    코코무
    BFS
    DP
    그리디
    특수문자 코드
    spa fallback
    라이브러리 제작
    완전탐색
    이분탐색
    storybook
    Git
    gpt-error-analyzer
    프로그래머스
    llm
    GPT
    merge
    CloudFront
    cogroom
    배포
    DFS
    javascript
    html
    s3
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
seio924
[ 백준 ] 2961 도영이가 만든 맛있는 음식 - JavaScript

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.