강의실/정보영재

정보올림피아드 초등부 2번

정보올림피아드 초등부 2번

정보올림피아드 초등부 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 의 값에서 앞뒤의 위치값을 계산하여 나온순서 위치에 작은 값을 계산하여 거리를 구한다.



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



이 장소를 Daum지도에서 확인해보세요.
인천 서구 당하동 1028-2 장원프라자 502호
도움말 Daum 지도
5 0
  • 잉여토기 2018.08.09 12:13 신고    

    해당 문제 풀다 맘대로 안 풀려 고민하신 분들에게 빛이 될 정보네요.

  • 휴식같은 친구 2018.08.09 14:46 신고    

    어려운 문젠데요?ㅎㅎ
    전 포기하고 갑니다.ㅋㅋ
    즐거운 하루 보내세요~^^

  • 버블프라이스 2018.08.09 18:32 신고    

    이 대회 문제들을 계속해서 풀이 관련 글을 올려주셔서 봤더니 문제들이 흥미롭네요^^
    2018년 정보올림피아드 전국대회 초등부 2번 화살표 문제 풀이를 해주셔서 학생분들은 이것을 참고하시고 본인의 것으로 만들어 시험때 꼭 푸시길 바랍니다.

  • 몰드원 2018.08.10 06:47 신고    

    벌써 금요일 이네요
    즐거운 금요일 보내시고 포스팅 잘 보고 갑니다

  • 핑구야 날자 2018.08.10 06:51 신고    

    출시된 문제를 풀어 보면 아무래도 도움이 많이 되겠죠