백준 5904번 Moo 게임 풀이/코드 (파이썬)

코드만 궁금하신 분은 링크

GitHub - Rhyankwon/algorithms

 

문제 설명 고?

 

문제에는 0번째에 m o o 라는 문자열이 주어지고, 순서가 반복될수록 이와 비슷한 모양이 계속해서 반복되게 된다. 그리고 여기에는 규칙이 있다. 말보다 보여주는게 나음

 

0번째 :  m o o

1번째 :  m o o m o o o m o o = [ 0번째 문자열 ]  m o o o  [ 0번째 문자열].

           사이 m o o o을 넣는 규칙은, m을 우선 무조건 붙인다. 그리고 o 갯수는 1 + 2. (n번째면 n +2 개가 됨)

n번째 : [ n-1번째 문자열] m o o o .. o o (n+2개의 o) [ n-1번째 문자열]

 

그리고 숫자 n이 입력되면 n번째 문자열의 n 번째 문자를 반환하면 됨! 설명이 잘 됫는지 모르겠지만... 누가 이 글을 보면 문제를 어차피 보고 왓을거같아서 이정도면 충분한거같다.

 

우선 나는 한번 풀었는데 거기에서 메모리초과가 떠서 다시 풀었다. 첫번째 풀이는 그냥 직관적?인 느낌으로 풀었다. 숫자 n이 입력되면 n번째 문자열까지 만들고 n-1째 문자 반환하기. 근데 보니까 범위가 10^9까지라서 메모리 오류가 뜨게 생기긴 했다; 그래서 길이만 가지고 품

 

내 찐 풀이:

 

1. n-1번째 문자열이 앞에 계속 들어가는 구조라, 만약 문자열의 길이가 n을 넘어가면 문자열의 총 길이가 백만이든 천만이든 n까지의 값은 똑같음.

2. 따라서 길이가 입력값 n보다 큰 문자열이 생성되면 문자열 생성을 멈추고 그 때부터 인덱스 찾는걸 통해서 그냥..풀면되는데..

3. 위에 보면 문자열은 앞부분, 가운데부분, 뒷부분 이렇게 세 부분으로 구성되게 된다. 하여, 지금 인덱스가 그 세부분 중 어디에 있는지 확인해보고

3-1. 만약 가운데에 있으면 바로 m인지 o인지 반환

3-2. 만약 앞부분에 있으면 n-1째 문자열의 몇번인지 로 다시 탐색

3-3. 만약 뒷부분에 있으면 앞쪽 길이만큼 다 빼버리고 n-1째 문자열에서 몇번인지 다시 탐색.

 

이해가 안되면 그냥  코드를 보면 된다. 인덱스 쪽이 헷갈리는것만 빼면 풀기 어려운 문제는 아님 ㅎㅎ 잘 풀린당

 

--------잡담----------

 

사실 처음에 잘못 풀었을 때 dp로 풀어야겠다는 감이 오긴했는데 그냥 검색해보고 풀었다. 다른 사람 풀이 보니까 대충 이런식으로 풀라고 해서.. 코드를 참고하고 푼건 아니라서 사실 내가 푼게 맞긴 한데 그래도 찜찜해 ㅠ 요새 순전히 내 힘으로 푸는 문제들이 별로 없어서.. 

 

문제를 풀면 풀수록 내가 얼마나 모자란지 느껴진다. 내년에 어디라도 붙을 수 있을까..?