(C++) - 백준(BOJ) 17265번 : 나의 인생에는 수학과 함께

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

17265번: 나의 인생에는 수학과 함께

완전탐색(brute force) 문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

 1. 바둑판 정보를 입력할 char형 이차원 배열 board, maxD, minD, n을 선언합니다.

 2. n을 입력 후 바둑판의 정보를 board에 입력합니다.

 

📔 풀이과정

dfs를 수행하면서 밟은 바둑판의 칸 정보를 string s에 저장하다가 (n - 1행, n - 1열)에 도착했을 때 s를 통해 정보를 parsing 후 계산해 답을 반환해줍니다. 최댓값을 뽑아내는 dfs, 최솟값을 뽑아내는 dfs를 option을 두어 각각 maxD, minD에 결과값을 저장합니다.

 

📔 정답출력

maxD, minD를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
char board[5][5];
int maxD ,minD , n;

int cal(int a, char op, int b){
    if(op == '+') return a + b;
    if(op == '-') return a - b;
    if(op == '*') return a * b;
    return 0;
}

int res(string s){
    int result = s[0] - '0';
    for(int i = 1; i < s.size(); i += 2)
        result = cal(result, s[i], s[i+1] - '0');
    return result;
}

int dfs(int r, int c, string s, int option){
    if(0 > r || r >= n || 0 > c || c >= n) return !option ? -INF : INF;
    if(r == n - 1 && c == n - 1) return res(s);
    int ret = !option ? -INF : INF;

    s.push_back(board[r+1][c]);
    if(!option) ret = max(ret,dfs(r + 1, c, s, option));
    else ret = min(ret,dfs(r + 1, c, s, option));
    s.pop_back();

    s.push_back(board[r][c + 1]);
    if(!option) ret = max(ret,dfs(r, c + 1, s, option));
    else ret = min(ret,dfs(r, c + 1, s, option));
    s.pop_back();
    
    return ret;
}

int main(){
    cin >> n;

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            cin >> board[i][j];

    string s = "";
    s += board[0][0];
    maxD = dfs(0, 0, s, 0);
    s = "";
    s += board[0][0];
    minD = dfs(0, 0, s, 1);
    cout << maxD << ' ' << minD;
}