1541번 - 잃어버린 괄호
안녕하세요. 문제를 풀면서 틀렸습니다를 접하여 그간의 질문글에서 나온 반례나 고려하지 못했던 부분들에 대한 처리를 다 한 것 같은데도 틀렸습니다 를 접하여 반례에 대한 도움을 얻고자 합니다.
문제 풀이는 다음과 같습니다.
제가 생각했던 방식은 '- 이후에 나오는 값들은 다시 -가 나오기 전까지 괄호를 취해주면 최솟값을 구할 수 있다' 입니다.
예를 들면, 50-60+60+70+70-50 의 경우, 50-(60+60+70+70)-50 이 최소가 될 것입니다.
먼저 -로 문자열을 파싱한 이후, 괄호를 취했을 때와 취하지 않았을 때의 값을 각각 구합니다. 그리고 그 차이를 differences 라는 배열에 저장해 놓습니다.
differences를 정렬하면, 괄호를 적용했을 때와 적용하지 않았을 때의 효과가 오름차순으로 정렬이 됩니다.
다만, 최대 문자열의 길이가 이미 정해져 있으므로, 괄호를 몇 쌍 까지 적용할 수 있는지에 대한 maximum을 미리 구해 놓고, differences가 큰 순대로 괄호를 적용한 다음, 괄호를 다 쓴 경우에는 괄호를 취하지 않았을 경우를 계속 더했습니다.
여러 반례를 적용해 봤는데, 생각한대로 나와서 혼란이 오네요.
머리 식히고 다시 보겠지만, 일단은 고수분들의 의견을 듣고 싶습니다.
긴 글 읽어주셔서 감사합니다.
아, 부끄럽게도 질문글을 올리자마자 바로 잘못된 로직을 찾았습니다.
역시 누군가에게 설명하면서 정리하는게 도움이 되네요.
수정한 부분은 아래 소스에 주석으로 표기해 놓았습니다.
괄호를 칠 수 있는 곳이 최대 몇 번인지 체크 해 놓고 사용을 안 한 탓이네요.
댓글을 작성하려면 로그인해야 합니다.
win198978 4년 전
안녕하세요. 문제를 풀면서 틀렸습니다를 접하여 그간의 질문글에서 나온 반례나 고려하지 못했던 부분들에 대한 처리를 다 한 것 같은데도 틀렸습니다 를 접하여 반례에 대한 도움을 얻고자 합니다.
문제 풀이는 다음과 같습니다.
제가 생각했던 방식은 '- 이후에 나오는 값들은 다시 -가 나오기 전까지 괄호를 취해주면 최솟값을 구할 수 있다' 입니다.
예를 들면, 50-60+60+70+70-50 의 경우, 50-(60+60+70+70)-50 이 최소가 될 것입니다.
먼저 -로 문자열을 파싱한 이후, 괄호를 취했을 때와 취하지 않았을 때의 값을 각각 구합니다. 그리고 그 차이를 differences 라는 배열에 저장해 놓습니다.
differences를 정렬하면, 괄호를 적용했을 때와 적용하지 않았을 때의 효과가 오름차순으로 정렬이 됩니다.
다만, 최대 문자열의 길이가 이미 정해져 있으므로, 괄호를 몇 쌍 까지 적용할 수 있는지에 대한 maximum을 미리 구해 놓고, differences가 큰 순대로 괄호를 적용한 다음, 괄호를 다 쓴 경우에는 괄호를 취하지 않았을 경우를 계속 더했습니다.
여러 반례를 적용해 봤는데, 생각한대로 나와서 혼란이 오네요.
머리 식히고 다시 보겠지만, 일단은 고수분들의 의견을 듣고 싶습니다.
긴 글 읽어주셔서 감사합니다.