✓

태그:

7. 문자열

주어진 문자열의 각 문자에 대해 다이얼 숫자를 매핑한 후 이를 합산하는 문제입니다. 각 문자에 대해 조건문을 이용하여 어느 다이얼에 위치할 지 체크합니다. 이 체크한 값에 다이얼 누르는 시간 - 다이얼 숫자를 각각 더한 후 모두 더해준 뒤 출력합니다.

이 문제를 다항식 회귀를 이용하여 푸는 방법이 있습니다. 문자와 숫자가 매핑된 것을 보면 이차함수로 근사하여 풀 수 있을 것 같습니다. 아래의 과정을 통해 근사를 할 수 있습니다.

\[X=\begin{pmatrix} 1&x_1&x_1^2\\ 1&x_2&x_2^2\\ &...&\\ 1&x_n&x_n^2 \end{pmatrix} =\begin{pmatrix} 1&1&1\\ 1&2&4\\ &...&\\ 1&26&676 \end{pmatrix}, Y=\begin{pmatrix} y_1\\y_2\\...\\y_n \end{pmatrix} =\begin{pmatrix} 3\\3\\...\\10 \end{pmatrix}, \beta=\begin{pmatrix} \beta_0\\\beta_1\\\beta_2 \end{pmatrix}\\ Y=X\beta+\epsilon\\ \hat{\beta}=(X^T X)^{-1} X^T Y \simeq \begin{pmatrix}2.307\\0.36\\-0.002\end{pmatrix}\\ \hat{Y}=X\hat{\beta}\]

이렇게 구한 \(\hat{Y}\)는

[2.665, 3.019, 3.369, 3.715, 4.057, 4.395, 4.729, 5.059, 5.385, 5.707, 6.026, 6.340, 6.650, 6.957, 7.259, 7.557, 7.852, 8.142, 8.429, 8.711, 8.990, 9.264, 9.535, 9.802, 10.064, 10.323]

의 값을 가집니다. 이걸 모두 정수 범위로 반올림하면

[3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10]

이 됩니다. 즉, \(\hat{\beta}\) 값과 알파벳의 아스키 코드 값을 사칙연산만을 이용하여 값을 뽑을 수 있는 것입니다. 이를 통해 더욱 빠른 시간 내에 답을 도출할 수 있습니다.

이것을 이용한 코드는 여기서 볼 수 있습니다.

---

사칙연산과 min 함수를 이용해서 어떻게 숏코딩 Python 1위를 기록했습니다! 이 코드는 선형 회귀를 이용하여 X, Y, Z를 제외한 나머지 알파벳에 들어맞는 적절한 일차함수를 찾은 후 계수를 적절히 바꾸어 코드에 들어가는 상수의 길이가 최소화되게끔 바꾸어서 풀었습니다. X, Y, Z는 min 함수를 이용하여 W와 같은 값을 가지게 한 값을 일차함수에 넣어 올바른 시간 값을 얻은 것이죠. 숏코드 순위

소스 코드

언어	코드	시간	비고
Python 3	코드(Github) / 코드(백준)	2020-03-25 13:33:16
Python 3	코드(Github) / 코드(백준)	2020-03-25 14:34:14	숏코딩, 51바이트

---