Problem/Brute force

[C/C++] BOJ 3/2 코딩테스트 대비 모의고사 A번 - 계란으로 계란치기

지무룩 2019. 3. 2. 17:28

BOJ 3/2 코딩테스트 대비 모의고사 A번 - 계란으로 계란치기




문제 링크 : https://www.acmicpc.net/contest/problem/396/1







나의 풀이




계란이 들어있는 판을 모두 탐색하면서,


내가 들고있는 계란이 아니고 깨진 계란이 아니면 들고 있는 계란과 충돌시킨다.


충돌시킨 후 각 계란의 내구성과 깨짐 여부를 갱신시킨다.


다음에 들 계란을 오른쪽으로 이동하며 깨지지 않은 계란으로 결정한 후, 이를 반복한다.


모든 계란이 깨졌거나 마지막 계란까지 탐색을 마친 경우, 깨진 계란의 개수를 계산하여 답을 갱신한다.




나의 코드




Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_problemA/BOJ_problemA.cpp




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
// BOJ 3/2 코딩테스트 대비 모의고사 A번 - 계란으로 계란치기
#include<iostream>
using namespace std;
 
int N, S, W, ans;
bool flag;
struct e
{
    int broken;
    int durability;
    int weight;
}typedef EGG;
 
int arr[9];
EGG egg[9];
 
// 깨진 계란 복구하기
void crushback(int e1, int e2)
{
    egg[e1].durability += egg[e2].weight;
    egg[e2].durability += egg[e1].weight;
    if (egg[e1].durability > 0) egg[e1].broken = 0;
    if (egg[e2].durability > 0) egg[e2].broken = 0;
    return;
}
// 계란 깨뜨리기
void crush(int e1, int e2)
{
    egg[e1].durability -= egg[e2].weight;
    egg[e2].durability -= egg[e1].weight;
    if (egg[e1].durability <= 0) egg[e1].broken = 1;
    if (egg[e2].durability <= 0) egg[e2].broken = 1;
    return;
}
// 깨진 계란의 개수를 세는 함수
int findnumbroken()
{
    int v = 0;
    for (int i = 0; i < N; i++)
    {
        if (egg[i].broken == 1) v++;
    }
    return v;
}
void simulate(int idx)
{
    flag = false;
    // 갱신
    if (idx >= N)
    {
        int val = findnumbroken();
        if (ans < val) ans = val;
        return;
    }
 
    // 깨지지 않은 계란 하나 골라 깨뜨리기
    for (int i = 0; i < N; i++)
    {
        // 깨뜨리기
        if (i != idx && egg[i].broken == 0) {
            crush(idx, i);
            int k = idx + 1;
            while (egg[k].broken == 1) k++;
            simulate(k);
            crushback(idx, i);
            flag = true;
        }
    }
    // 더 이상 깨뜨릴 수 있는 계란이 없을 때, 값 갱신
    if (!flag)
    {
        int k = idx + 1;
        while (egg[k].broken == 1) k++;
        simulate(k);
    }
    return;
}
 
int main()
{
    cin >> N;
    for (int i = 0; i <= N; i++)
    {
        egg[i].broken = 0;
        egg[i].durability = 0;
        egg[i].weight = 0;
    }
 
    for (int i = 0; i < N; i++)
        cin >> egg[i].durability >> egg[i].weight;
 
    simulate(0);
 
    cout << ans;
}
cs


저작자표시