백준 5557번 1학년

< 백준 5557번 1학년 - 마포 코딩박 >

사용한 알고리즘: DP


 N개의 수와 덧셈, 뺄셈 연산으로 만들 수 있는 올바른 등식수를 구하는 문제였습니다.
 마지막 수 앞에는 '=' 이 들어가야 합니다.

문제풀이는 다음과 같습니다.

(1) (코드 6~7)
 'dp[x][temp]: "x번째 도착, 이전 계산값이 temp인(x-1번째 까지 계산) 상태" 에서 만들 수 있는 올바른 등식 수' 로 dp 값을 설정해 주었습니다.

(2) (코드 8~28, 34~35)
 dp값을 계산해주는 함수를 만들어 줍니다.
 dp 설정에 따르면 dp[i][temp] = dp[i+1][temp+(i번째 값)] + dp[i+1][temp-(i번째 값)] 이겠죠.
 시작은 ( 2번째 도착, 이전계산값(=1번째 값)) 으로 하면 됩니다.