2018년 정보올림피아드 전국대회 초등부 2번 화살표 문제 풀이

문제풀이) 수평선에서 자기 자신과 가장 가까운 거리의 같은 색깔을 찾는 문제이다. 가령 입력예 1 에서  0번의 색깔은 1이다 이것과 가장 가까운 색깔 1의 위치는 3 이다 따라서 0의 거리는 3 3번의 가장 가까운 거리는 0 번과 5번 중에서 가까운 5번이다 따라서 거리는 2 5번의 가장 가까운 거리는 3번 따라서 거리는 2 풀이1) 색깔별로 바로 이전에 나온 위치를 저장해 놓고 자신의 위치에서 바로 이전의 같은색깔의 거리를 저장해 놓는다. 만약 처음 나오는 경우는 무한값(최대값)을 설정해 놓는다. 그리고 다음에 나오는 색상 (바로 이전에 나온 위치에서 바라보면 현재의 위치가 바로 이전에 나온 위치에서의 다음 위치이다.) 을 비교 하여 이전의 거리보다 짧다면 현재 위치의 거리를 갱신한다.  이렇게 하면 N번 만에 계산할 수 있다. 예제 소스는 네이버 블로그에 올렸습니다. 하지만 예제 소스를 먼저 확인 하지는 마시고 먼저 충분히 고민한 후에 직접 만들어 보시는 것을 권해 드립니다. 소스위치(서로이웃에게만 공개합니다.) https://blog.naver.com/icon003/221332125495 풀이2) N이 5000 이므로 벡터 배열을 이용해서 해당 색상별로 나오는 위치를 연결시켜 놓을 수 있다. 가령 1번 색상인 경우  Color[1] 위치에 -> 0 ->3 ->5 와  같은 자료구조로 연결을 할 수 있다. 각 Color 별 Sort 하여 처음 부터 순서대로 계산하여 나가도 된다. 해당 Color 의 값에서 앞뒤의 위치값을 계산하여 나온순서 위치에 작은 값을 계산하여 거리를 구한다.

정보올림피아드 문제 풀이 리스트 정리