16637번 - 괄호 추가하기
...논리는 다음과 같습니다. 피연산자가 n개, 연산자가 n-1개 있을 때,
dp[k] = '첫 번째부터 k번째까지 총 k개 피연산자를 이용하여 계산하였을 때 나올 수 있는 계산 값 중,
dp[k][0] = 양수 최댓값
dp[k][1] = 음수 최솟값
dp[k][2] = 양수 최솟값
dp[k][3] = 음수 최댓값을 저장하고 있습니다.
이 4개에 대해 각각 dp[k - 1] 및 1개의 추가 피연산자 계산 값과 dp[k - 2] 및 2개의 추가 피연산자 계산 값을 고려했습니다.
즉, 1+5*3이라면, 앞 2개의 최댓값인 6에 3을 곱하는 것과, 앞 1개의 최댓값인 1에 (5*3)을 더하여 dp[3][0]에는 18이, dp[3][2]에는 16이 들어가게 하였습니다.
질문 게시판의 모든 반례와, 제가 개인적으로 만들어본 랜덤 테스트케이스 몇 개도 잘 돌아가서 이젠 정말 질문밖에 답이 없었습니다... 부디 도와주세요 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ
https://ideone.com/Xtg4dE
이럴수가 vs에서만 제대로 나왔었네요... 감사합니다... 근데 여전히 오답이군요...
댓글을 작성하려면 로그인해야 합니다.
surung9898 3년 전 1
키사마!!!!!!!!!!!!!!!!!!!!!!!!
...논리는 다음과 같습니다. 피연산자가 n개, 연산자가 n-1개 있을 때,
dp[k] = '첫 번째부터 k번째까지 총 k개 피연산자를 이용하여 계산하였을 때 나올 수 있는 계산 값 중,
dp[k][0] = 양수 최댓값
dp[k][1] = 음수 최솟값
dp[k][2] = 양수 최솟값
dp[k][3] = 음수 최댓값을 저장하고 있습니다.
이 4개에 대해 각각 dp[k - 1] 및 1개의 추가 피연산자 계산 값과 dp[k - 2] 및 2개의 추가 피연산자 계산 값을 고려했습니다.
즉, 1+5*3이라면, 앞 2개의 최댓값인 6에 3을 곱하는 것과, 앞 1개의 최댓값인 1에 (5*3)을 더하여 dp[3][0]에는 18이, dp[3][2]에는 16이 들어가게 하였습니다.
질문 게시판의 모든 반례와, 제가 개인적으로 만들어본 랜덤 테스트케이스 몇 개도 잘 돌아가서 이젠 정말 질문밖에 답이 없었습니다... 부디 도와주세요 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ