[백준/PYTHON] 17265 나의 인생에는 수학과 함께

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

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

문제 분석

난이도

골드5

분류

그래프 탐색, 브루트포스

들어가기 전에

파이썬으로 풀면 eval로 굉장히 쉽게 풀 수 있다고 생각했지만 그런 문제는 아니였다. 

문제

세현이의 인생의 목표는 1분 1초 모든 순간 수학과 함께 살아가는 것이다. 그렇기 때문에 매일 수학을 생각하면서 살아가고 있다. 세현이는 밥을 먹을 때도 쌀알의 수를 계산하여 칼로리를 바로 계산하고 한걸음 한걸음 보폭을 계산하여 자신의 활동량을 확인하며 인생의 목표를 실행하며 살아가고 있다.  그런 세현이는 매일 학교를 가면서 지나가는 길에도 수학을 적용시키고 싶었다.

세현이네 집에서 학교까지 가는 길은 N x N 크기의 바둑판과 같다. 그리고 각 블록은 1x1 정사각형으로 구분 지을 수 있다. 세현이는 그 블록마다 숫자와 연산자가 존재한다고 생각해서 임의의 숫자와 연산자를 각 블록에 넣어 바둑판을 만들었다.

세현이는 학교에서 집으로 가는 경로에서 만나는 숫자와 연산자의 연산 결과의 최댓값과 최솟값을 구하려고 한다. 세현이는 항상 자신의 집 (1, 1)에서 학교 (N, N)까지 최단거리로 이동한다. 최단거리로 이동하기 위해서는 오른쪽과 아래쪽으로만 이동해야 한다.

세현이는 이 길을 걸으면서 최댓값과 최솟값을 암산하다가 교통사고를 당해 현재 인하대학교 병원에 입원했다. 아픈 세현이를 위해 최댓값과 최솟값을 구해주자.

입력

첫 번째 줄에는 지도의 크기 N이 주어진다. (3 ≤ N ≤ 5, N은 홀수) 

그 다음 N 줄에는 N개의 숫자 또는 연산자가 빈칸을 사이에 두고 주어지며, 세현이네 집 (1, 1)과 학교 (N, N)는 반드시 숫자로 주어진다.

그리고 숫자 다음에는 연산자, 연산자 다음에는 숫자가 나오도록 주어진다. 주어지는 숫자는 0이상 5이하의 정수, 연산자는 (‘+’, ‘-’, ‘*’) 만 주어진다.

출력

연산 결과의 최댓값과 최솟값을 하나의 공백을 두고 출력한다. 연산자 우선순위는 고려하지 않는다.

 

문제 풀이

 

풀이

연산자 우선순위를 고려하지 않으므로, 이동하는 족족 계산해주면 된다.

소스코드

from sys import stdin
input=stdin.readline

def dfs(x,y,v):
    global ans,ans2
    if x==y==n-1:
        ans=max(ans,eval(v))
        ans2=min(ans2,eval(v))
        return
    try:
        dfs(x+1,y,v+arr[x+1][y] if (x+y)%2==0 else str(eval(v+arr[x+1][y])))
    except:
        pass
    try:
        dfs(x,y+1,v+arr[x][y+1]if (x+y)%2==0 else str(eval(v+arr[x][y+1])))
    except:
        pass



n=int(input())
ans=-10**10
ans2=10**10

arr=[list(input().rstrip().split()) for i in range(n)]

dfs(0,0,arr[0][0])
print(ans,ans2)

후기

문자열 연산 연습이나 그래프 탐색 연습용으로 적절하다고 생각했다.