백준 3954번 Brainf**k 인터프리터

문제 링크입니다: https://www.acmicpc.net/problem/3954

3954번: Brainf**k 인터프리터

개요

주어진 조건대로만 풀면 되는 문제였지만 무한루프라는 정의에 대해 생각해봐야하는 문제였습니다.기존에 작성한 코드는 시스템 케이스 데이터들이 약해서 운이 좋게 AC를 받았지만, 고수분들의 채점 정정 요청에 따라 재채점 결과 WA를 받았습니다.

 

기존 코드는 아래와 같습니다.

 

기존의 문제점

기존 코드의 문제점은 프로그램 명령어를 5천만번만 실행한 상태로 loop를 찾았다는 점입니다.

 

문제의 조건을 다시 한번 읽어봅시다.

프로그램이 명령어를 50,000,000번 이상 수행한 경우, 프로그램은 항상 종료되었거나 무한 루프에 빠져있다. 무한 루프일 경우, 해당 루프는 적어도 한 번 실행이 완료된 상태이며, 한 번의 무한 루프에서 실행되는 명령어의 개수는 50,000,000개 이하이다.

 

정리를 하자면, 명령어를 5천만번 실행을 한 상태에서 무한루프에 들어온 상태라면 다시 5천만번 실행을 하는 경우가 있습니다. 따라서, 기존 코드처럼 5천만번만 실행할 것이 아니라 1억번을 실행했어야하는 것입니다.

 

변경된 코드

여기서 핵심은 무한 루프의 왼쪽 괄호 인덱스는 프로그램 인덱스의 최솟값이라는 점입니다! (99 ~ 102 라인 참고)

 

 

비고

해당 문제가 재채점됐다는 것을 알려주신 코딩중독님께 감사의 말씀을 남깁니다.

그리고, 무한루프가 유일하다는 것을 멋지게 증명해주신 jh05013님 존경합니다.

해당 증명에 관심이 있으시다면 아래 링크를 참고해주세요.

www.acmicpc.net/board/view/50721

글 읽기 - 무한 루프의 정의를 제안합니다.