[백준] 16987번 계란으로 계란치기

2025. 2. 2. 19:24·백준 문제/백트래킹

문제: 16987번: 계란으로 계란치기

basic-algo-lecture/workbook/0x0C.md at master · encrypted-def/basic-algo-lecture

 

basic-algo-lecture/workbook/0x0C.md at master · encrypted-def/basic-algo-lecture

바킹독의 실전 알고리즘 강의 자료. Contribute to encrypted-def/basic-algo-lecture development by creating an account on GitHub.

github.com

 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iomanip> // setprecision을 사용하기 위한 헤더
#include <climits>
#include <list>
#include <sstream>

using namespace std;

int maxCnt = -1;
int n;
pair<int, int> eggs[8]; // max 가 8

void Funct(int idx) {
	// 마지막 계란에 도달했으면 빠져 나가기
	if (idx >= n) {
		int tmpCnt = 0;

		for (int i = 0; i < n; i++)
			if (eggs[i].first <= 0)
				tmpCnt++;

		if (tmpCnt > maxCnt)
			maxCnt = tmpCnt;

		return;
	}

	// 현재 계란이 깨졌는지 확인. 깨졌으면 다음 계란을 집어들어.
	if (eggs[idx].first <= 0) 
		Funct(idx + 1);
	else {
		// 현재 계란 안 깨졌으면 얘로 계란 쳐
		// 자기 자신이랑 이미 깨진 계란 제외하고
		bool flag = false; // 내려쳤는지 안쳤는지 판단
		for (int i = 0; i < n; i++) {
			if (i == idx || eggs[i].first <= 0) continue;

			// 계란끼리 부딪히면 내구도 깎임
			eggs[i].first -= eggs[idx].second;
			eggs[idx].first -= eggs[i].second;

			Funct(idx + 1);

			eggs[i].first += eggs[idx].second;
			eggs[idx].first += eggs[i].second;
		}

		// 칠 계란이 없으면 걍 종료하는거
		if (flag == false)
			Funct(n);
	}
}

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

	cin >> n;

	for (int i = 0; i < n; i++) {
		int s, w;
		cin >> s >> w;
		eggs[i] = make_pair(s, w);
	}

	Funct(0);
	cout << maxCnt;

	return 0;
}

 

문제에서 준 조건대로 백트래킹 이용해서 풀면 된다.

 

맨 오른쪽 계란에 도달하면 현재까지 깨진 계란의 개수를 카운트 하고, maxCount 에 반영한 후 빠져나오도록 했다.

 

맨 오른쪽 계란에 도달하지 않았으면 계속 조건대로 하면 된다. 현재 계란이 깨졌는지 확인하고 깨졌다면 다음 계란을 집어든다. 만약 깨지지 않았다면 현재 계란으로 다른 계란을 친다. 다른 계란을 치고 나서는 현재 들고 있었던 계란의 다음 계란을 들어야 함.

 

만약 더이상 칠 계란이 없으면 그냥 종료해야 하니까 flag 변수를 이용했다. flag 값으로 판단 한 후 Funct(n) 을 호출했다.

'백준 문제/백트래킹' 카테고리의 다른 글
  • [백준] 6603번 로또
  • [백준] 15666번 N과 M(12)
  • [백준] 15665번 N과 M(11)
  • [백준] 15664번 N과 M(10)
dubu0721
dubu0721
dubu0721 님의 블로그 입니다.
  • dubu0721
    dubu0721 님의 블로그
    dubu0721
  • 전체
    오늘
    어제
    • 분류 전체보기 (351)
      • 프로그래밍언어론 정리 (5)
      • 컴퓨터네트워크 정리 (5)
      • 알고리즘&자료구조 공부 (64)
        • it 취업을 위한 알고리즘 문제풀이 입문 강의 (60)
        • 학교 알고리즘 수업 (3)
        • 실전프로젝트I (0)
      • 백준 문제 (204)
        • 이분탐색 (7)
        • 투포인트 (10)
        • 그래프 (11)
        • 그리디 (24)
        • DP (25)
        • BFS (21)
        • MST (7)
        • KMP (4)
        • Dijkstra (3)
        • Disjoints Set (4)
        • Bellman-Ford (2)
        • 시뮬레이션 (3)
        • 백트래킹 (15)
        • 위상정렬 (5)
        • 자료구조 (25)
        • 기하학 (1)
        • 정렬 (11)
        • 구현 (8)
        • 재귀 (8)
        • 수학 (8)
        • 트리 (1)
      • 유니티 공부 (11)
        • 레트로의 유니티 게임 프로그래밍 에센스 (11)
        • 유니티 스터디 자료 (0)
        • C# 공부 (0)
      • 유니티 프로젝트 (48)
        • 케이크게임 (13)
        • 점토게임 (35)
      • 언리얼 공부 (10)
        • 이득우의 언리얼 프로그래밍 (10)
      • 진로 (1)
      • 논문 읽기 (1)
  • 블로그 메뉴

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

  • 공지사항

  • 인기 글

  • 태그

    언리얼
    유니티 공부 정리
    C#
    해시
    그래프
    자료구조
    이득우
    스택
    BFS
    유니티 프로젝트
    맵
    오블완
    우선순위큐
    시뮬레이션
    티스토리챌린지
    바킹독
    백트래킹
    dp
    재귀
    큐
    투포인터
    이분탐색
    백준
    골드메탈
    유니티
    이벤트 트리거
    수학
    그리디
    레트로의 유니티 프로그래밍
    정렬
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
dubu0721
[백준] 16987번 계란으로 계란치기
상단으로

티스토리툴바