Red Salmon

출처 : 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문자가 안된다는 점이었다. 그렇다면 폭발문자열만 자주 사용해주어도 되겠다고 생각하여 진행하였다.

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

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

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

이 문제의 경우 DFS, BFS 도 가능할것 같은 문제인데 n이 400이고 결국 모든 간선에대하여 체크해야하므로 플로이드 알고리즘을 쓰는게 더 간단한것이라고 생각했다. 

DFS나 BFS로 푼다면 조금 복잡해질것같다. 기본적으로 DP를 사용해야만 DFS는 접근이 가능할테고, BFS역시 시간문제에서 벗어나려면 상당히 애먹을것 같다. 

암튼 간단히 플로이드를 쓰면되는데 어처구니 없게 이 문제도 실수를 하였다. 날이 더워서그런지 실수가 잦다.

나의 실수는 플로이드 알고리즘에서 범위값을 for(int i=0; i<n; i++)로 잡았는데 당연히 오답이다. 왜냐면 인풋이 1부터 n까지 들어오기 때문이다. 

이 오류도 찾는데 상당히 시간이 지체되었다...ㅠㅠ

날이 더우니 정말 힘들다..ㅠㅠ