이모티콘 할인행사 문제 실패 회고 - 왜 DFS를 떠올리지 못했을까

문제 개요

• 문제명: 이모티콘 할인행사 (프로그래머스 Lv2)
• 핵심 키워드: 완전탐색, DFS, 조합, 시뮬레이션
• 문제 설명 요약
  
  • 이모티콘 n개가 있음. 각 이모티콘은 10, 20, 30, 40% 할인율 중 하나를 가짐.
  • m명의 사용자가 있음. 각 사용자는 할인율 기준, 이모티콘 플러스 가입 기준 금액을 가짐.
  • 할인율을 조합하여,
    • 이모티콘 플러스 서비스 가입자 수 최대화
    • 그 기준이 같다면 이모티콘 판매액을 최대화

---

이모티콘 할인행사 문제 회고: DFS를 떠올리지 못한 이유

1. 왜 실패했는가?

• 문제를 처음 봤을 때, 사용자 조건과 이모티콘 가격 조건만 복잡하게 보였고,
• “각 이모티콘에 대해 할인율을 결정해야 한다”는 구조를 단순 반복문이나 조건문으로 해결하려 함
• 결국 할인율 조합을 만들기 위한 DFS나 백트래킹 같은 접근 자체를 떠올리지 못함

---

2. 왜 DFS를 떠올려야 했는가?

• 할인율의 선택지가 고정: [10, 20, 30, 40] → 고정된 수의 선택지
• 각 이모티콘마다 하나의 할인율을 선택 → 모든 경우의 수를 탐색해야 함
• 따라서 “모든 조합을 순회해야 한다” = 완전탐색(DFS/백트래킹)이 정석적인 접근

이럴 땐 항상 “n개의 자리마다 m개의 선택지 → m^n의 조합” 구조인지 확인하자.

---

3. 다음엔 어떻게 떠올릴 것인가?

• 문제를 읽고 “조합” 또는 “모든 경우의 수를 따져야 하는가?” 먼저 체크할 것
• 다음 조건이 있다면 무조건 DFS/백트래킹 고려:
  • 각 항목마다 여러 선택지 존재
  • 모든 경우를 따져야 정답이 나옴
  • 최댓값/최솟값 조건이 있음 (ex. 최대 가입자 수, 최대 매출 등)

---

4. 포스트 후 보완할 점 (복기/보완할 항목)

• DFS로 모든 조합 탐색 문제 하나 더 풀어보기
• 조합을 떠올려야 할 조건 체크리스트 Notion에 정리해두기
• 조건 분기 복잡한 시뮬레이션 문제 정리한 블로그 1편 읽기

이 문제는 결국 DFS를 떠올렸다면 어렵지 않게 접근할 수 있었다.
실패했지만, 문제의 본질을 다시 파악하고 다음엔 더 빠르게 탐색 패턴을 적용해보려 한다.