BOJ 1541 잃어버린 괄호

이 문제는 +, - 밖에 없고, 이 식의 값을 최소로 만들어야 하므로 +끼리 다 괄호로 묶어서, 즉 -를 기준으로 부분을 나눠서 그 부분을 괄호로 묶어버린다. 그렇게 하면 주어진 식의 수들을 최대한 더하고 -를 붙이는 것이 되므로 최소값이 나올 것 같다. 알고리즘 분류를 보니 그리디 알고리즘으로 되어있다.

그리고 입력으로 주어진 식을 입력받을 때, 숫자가 0으로 시작할 수도 있다고 해서 문자로 받아야 하나 고민하다가 실험해 봤는데, 012 이런 숫자를 scanf("%d"로 받으면 알아서 12로 받아진다.

코드로 짜봐야겠다.
입력을 받으면서 바로 바로 계산하려고 했는데, 조금 까다로워서 미리 배열에 입력을 다 받아놓고 해보려고 한다. 길이도 최대 50인 식이 주어지므로.. 여유있게 부호와, 숫자를 저장할 길이가 50인 배열을 선언해서 하면될 것이다.

55-50+40+30+20+10-20+30+20-10 이라는 식이 있으면
일단 첫 번째 수인 55는 따로 받고, -50부터 배열에 받기 시작한다.
- 50
+ 40
+ 30
+ 20
+ 10
- 20
+ 30
+ 20
- 10
이렇게 배열에 저장될 것이고, 처음부터 더하기 시작해서 -가 나오기 직전까지의 숫자의 합을 구해서 -를 붙인다. +밖에 없다면 그냥 계속 더하면 된다.

이 문제를 풀다가 scanf로 입력을 받는 중에 문제가 좀 있었다.
 
원래 while문에서 scanf로 idx를 증가시켜가며 코드에서 6번째 줄처럼 입력받으려 했는데,
제대로 값이 들어가지 않아서 위의 짧은 코드로 실험해봤더니 scanf에서는 뒤쪽 변수를 먼저 처리하는 결과가 나왔다. idx++를 앞에 넣으면 즉, arr1[idx++] 이렇게 해야 원하는대로 나온긴 하는데 그것은 vim에서 했을 때이다. 즉 gcc를 썼을 때이고, visual studio 2010에서 하니까 바꿔도 제대로 안나온다.
(참고로 위의 코드는 vim이나 visual studio2010 이나 똑같이 나온다.)

slack에서 이 것에 대해 질문을 했더니 functionx님께서 컴파일러마다 결과가 다른 식으로 나올 것 같다고 답해주셨다.

결론은... 저런식으로 코드를 작성하지 않는 것이 답이다. 확실하게 scanf 밖에서 idx++을 해줘야겠다.

AC를 받긴 했는데, 맞은 사람 목록의 코드의 길이가 꽤 짧다. 다른 사람들 코드 구경 좀 해야겠다.

음 kks227님의 코드를 봤는데... 좀 충격이었다. 왜냐하면 코드도 매우 짧을 뿐 아니라 부호를 받는 코드가 없었기 때문이다... 헉...순간 다른 문제인가 했다. 정신을 집중해서 다시 보니 그냥 정수로 받으시는 거다... 아...-3 +5 이렇게 받을 수 있구나... 그렇지...
와... 게다가 +끼리 다 묶어서 -붙여주는 작업을 할 필요도 없다. 그냥 -가 하나라도 나오면 그 뒤는 모조리 -로 만들 수 있다. 그래서 그냥 -가 나온 이후(정수로만 받았으므로 음수가 나오면!)로는 그냥 절대값해준 값을 빼버리면 된다... 와... 정말 멋있는 것 같다.
난 -3 -4 이런건 정수로 받을 수 있다고 알고 있었는데 +3 +4 이런 것도 되는 거였구나.. 012 이런것도 12로 입력받아진다는 것도 알게되고, 이런 것도 알게되고..많이 알게되었다.
한 번 이렇게 또 짜봐야겠다. AC를 받았다. kks227님의 풀이가 정말 좋았다.