[Python] 18867번 편지 꼭 해다오

https://www.acmicpc.net/problem/18867

18867번: 편지 꼭 해다오

---

 

22/11/16

 

 

실랜디를 하다가 만나게 된 조금 어처구니없는 문제로, 많이 틀렸었었다.

 

레이팅이 된 문제이긴 한데, 약간 번외 문제 느낌이 들었어서 흥미롭게 풀었던 기억이 있다.

 

전형적인 구성적 문제이나, 그 조건이 문자열과 정수론이 결합된 독특한 문제여서 조금 애를 먹었다.

---

 

문제 접근 방식:

 

 

1바이트 단위로 끊어서 읽는데, 이 $i$번째 문자를 int로 캐스팅 한 값을 $x_i$라고 할 때, $\left ( \sum {x_{i}}^{814} \right )\ \mathrm{mod}\ 20200429 = 20200402$ 가 되도록 문자열을 구성하는 것이 문제의 핵심이다.

 

단, 990316바이트 이하로 문자열을 구성해야한다는 조건이 있다.

 

처음에 보고 너무 문제가 독특하고, 요상해서, 어떻게 풀어야 할지 감조차 오지 않았다.

 

일단, 처음 접근한 방법은 chr함수에 숫자를 넣으면 문자가 나온다는 사실에서 착안하여, for문을 사용하여 1부터 일일이 숫자를 넣어봤다.

 

근데 나머지가 단박에 20200402가 되는 문자는 없었다.

 

이를 통해, 문자를 여러 개를 사용해서 구성해야 된다는 것을 깨닫고 굉장히 난감했다.

 

처음 접근 방법은 다음과 같았다.

 

일단 우리가 만들고자 하는 $20200402$ 나머지와 제일 가깝도록 하게 나오는 숫자$N$을 찾기로 했다.

 

그러고 난 다음 chr($N$)을 출력하고, 이후에는 chr(1)에 해당하는 문자를 계속 반복해서 출력함으로써 나머지가 채워지도록 만들었다.

 

그렇게 했더니 틀렸습니다를 받았는데, 잘 생각해보니 그 문자 chr($N$)은 한자였는데, 한자는 1바이트가 아니라 2바이트라는 사실을 깨달아버렸었다.

 

이후 되도록이면 영어와 숫자에서만 찾도록 생각을 바꿨어야 했었다.

 

그렇게 바꾼 두번째 접근 방법은 다음과 같았다.

 

어떤 특정한 나머지들을 계속해서 더하면 나머지가 달라지면서 순환하다가 나머지가 $20200402$가 되도록 하는 순간이 나올 것이라고 생각했다.(문제 풀 당시에는 이렇게 생각했었고, 지금 와서 정당화를 시켜보면 $20200429$가 소수여서, 어떠한 나머지를 잡던지 항상 순환(모든 나머지를 다 훑고 지나감)한다는 것을 보일 수 있다.)

 

따라서, 'a~z, A~Z, 0~9'중에서 하나를 골라 나머지가 $20200402$가 되도록 같은 문자를 반복해서 출력하도록 했다.

 

근데, 총 길이가 990316바이트 이하여야 된다고 했으므로, 이 반복해서 출력하는 횟수가 990316번 이하인 문자를 골라서 출력하도록 했다.

 

근데, 파이썬으로 출력할 때의 주의할 점은 기본 print함수는 줄 바꿈 문자까지 출력하기 때문에 조심해야 한다는 점이다.

 

따라서 줄바꿈 문자를 없애도록 출력까지 해줘야 맞았습니다를 받을 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 18867번 편지 꼭 해다오
# 실랜디(문자열, 구성적, 정수론)
'''
접근 방법:
무작정 나열
'''
print('V'*856066, end = '')