Red Salmon

출처 : https://www.acmicpc.net/problem/10827

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/10827.java

이문제는 뭐 없다. 그냥 전부 계산하라는거다.

근데 이런건 자바가 최고다. C++로 하려면 구현해야할것들이 정~말 많다. 특히 곱셉의 경우 정~말 많다.

만약 코딩연습을 한다면 해볼만하지만...이미 다 알고..자바도 알고있기에 자바를 사용해서 풀었다.

다만 이번에 새로 안 함수가있다.

toPlainString()

나는 이 함수를 처음 사용해보았다. 아마 그전에도 써봤겠지만 기억을 못하고있다고 생각한다.

함수의 기능은 소수점 표기할때 중간에 자르지말고 전부 표기하라는 것이다. 

이것때문에 오답을 많이 맞다가 끝내 정답을 맞았다. 

할때마다 느끼지만... 걍 자바나 공부할걸 뭐한다고 C++을 공부해서 고생하는지 내 자신이 이해가 되지 않는다.

이번 하반기가 끝나고 취직하면 본업을 자바로 바꾸던지 해야겠다.

출처 : https://www.acmicpc.net/problem/11057

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/11057.cpp

DP문제이다. 규칙을 찾는데 약 30분정도가 걸렸다. 좀 오래걸린거 같다. 

알고리즘은 다음과 같다.

1. 0~9까지 수별로 오르막수를 구해본다.

2. 자리수를 하나씩 높이면 그 직전수의 모든 합이 0번째 인덱스가 되고 그다음부터는 직전 녀석과 그 이전의 0번째부터 시작하는 배열값을 하나씩 매칭시켜 빼면 다시 수가 나오고 또 전체합을 통해 구한다.

3. 팁이라면 나는 0부터 차근차근 더해나갔는데 이러니까 10007 로 나눌때 상당히 까다롭다. 결국 난 해결하지 못했고 알고리즘을 수정했다. 수정한 알고리즘은 어차피 앞수가 9로시작하면 무조건 모든수가 999 이런식으로 진행되야 하므로 1개뿐이라는 사실을 알고 여기서 시작한다. 

여기서 시작하여 다시 똑같이 진행하면 9번째수에는 최종 합이 담기게 된다. 

이 문제는 알고리즘을 찾는것보다 이 나누는 경우를 어떻게 처리해야하나를 가지고 상당히 고민했던 문제이다.

결국 발상의 전환이었지만, 사람이란게 생각에 갖히기 시작하면 전환하기 참 힘든것 같다.

출처 : https://www.acmicpc.net/problem/1967

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/1967.cpp

이 문제는 다풀어놓고 한참을 틀렸던 문제이다. 어처구니 없이 모든걸 만들어놓고 틀렸다 ㅠㅠ 왠지 작년에 본 삼성 SW역량 시험이 생각났다.. 다만들고 문장하나를 생각하지 못했던...

아무튼 문제는 가장 긴 구간을 찾는것이다. 

당연히 어떤 구간이 긴지 모르므로 전부 검색해봐야한다.

나는 DFS를 활용하였다. 여기서 내가 놓친 부분이 그것이다. 최대 지름을 구하는 문제이므로 2개의 길이만 필요하다. 

그리고 문제에서는 이진트리 느낌으로 보여졌는데, 실제 데이터에는 이진트리가 아닌것들도 많다. 자식노드가 여러개인경우 말이다.

사실 이정도면 미리 문제에서 알려줘야하지 않나..싶다.

알고리즘은 다음과 같다.

1. 벡터를 사용하여 연결된노드와 값을 입력한다.

2. 함수를 호출하는데 인자는 루트노드만 보내준다.

3. 각 루트노드에서 연결된 간선을 전부 탐색하고 그 간선의 값을 더해본다. 

4. 그리고  temp와 val[2]를 활용하여 val[2] 에는 가장 긴 2개의 녀석만 담아둔다.

5. 그 2개의 값의 합이 ans보다 큰지 비교를 한다.

6. 리턴은 그 2개에서 가장 긴녀석을 리턴한다.

이 과정이 반복이되면 딱 한번 모든 노드를 검색하게 되고 자연스레 답이 담기게 된다.

뭐랄까..예전엔 이런 DFS가 조금 힘들었는데 이젠 뭐...그냥 술술 풀린다. 그래도 실수한건 실수한거다. 문제를 잘 읽어야겠다.

출처 : https://www.acmicpc.net/problem/9935

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/9935.cpp

이 문제는 참 좋은 문제였다. 얼핏보면 매우 간단한 문제로 보였다. 그러나 자꾸 시간초과가 났고, 결국 문자열길이가 최대 백만이라는 점이 문제가 되고 있음 을 깨달았다.

초기 알고리즘은 폭발문자열을 찾고 그부분을 지우고 다시 찾고 지우고 이런식으로 진행했다. 생각해보니 찾는다는것 자체가 백만이라는 가정하에 너무도 늦게 찾을것 같았다.

그래서 생각한것이 스택처럼 다루는 것이다. 문자열을 하나씩 추가하고 끝문자를 기준으로하여 만약 폭발문자의 끝문자와 현재 스택으로쓰는 스트링의 끝문자가 같다면 폭발문자열과 같은지 그때만 비교를 하는것이다. 같다면 인덱스값을 조절하여 다시 저장하게 하는 방식으로 진행하였는데, 이렇게하니 상당히 빠른 속도를 보이며 정답을 맞았다.

이 키워드를 얻은 계기는 폭발문자열이 최대 40문자가 안된다는 점이었다. 그렇다면 폭발문자열만 자주 사용해주어도 되겠다고 생각하여 진행하였다.

참 괜찮은 문제라고 생각한다.