아희PS - solved.ac 빼빼로데이 이벤트 후기(+4문제 간단한 풀이, 최고 티어: GOLD I)

11월 11일 빼빼로데이를 기념해 solved.ac에서는 이벤트를 하나 했다. Gold 문제를 풀면 막대기를 하나 주고, Bronze/Silver/Platinum+Daimond/Ruby를 풀면 초코/화이트/민트/루비(?) 초콜릿을 주고, 같은 종류의 초콜릿 3개와 막대기를 조합해 빼빼로를 만드는 이벤트였다. BOJ 공식 아희 2위인 sciencepark이 이 이벤트를 그냥 지나칠 리 없었고, 나는 이 이벤트의 목표를 '아희만으로 빼빼로 하나 만들기'로 잡았다. Bronze를 3개 풀고, Gold를 1개 풀면 되는 것이었다. 그리고 나는 목표를 빼빼로데이 당일날 몇 시간 안에 해냈다. 이때 푼 문제들에 대해 간단하게 소개해보겠다.

이게 되네

13985번: Equality(Bronze IV)

1 + 2 = 3과 같은 등식이 주어지는데, 이 등식이 참이면 YES, 아니면 NO를 출력한다. +, =과 같은 문자는 필요가 없으니 '밯마'를 통해 바로 버려주고, 입력받은 3개의 숫자를 가지고 판단해주면 된다. YES와 NO의 출력은 문자열 to 아희 변환기를 사용하면 된다. 코드는 다음과 같다.

방밯마밯마방밯마밯마방파타파탸쿠처밡밡따밣다맣밝밡따밦다맣밡밡따반다맣해
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ밣밡따밦다맣밣밡따밝다맣해

입력-(c-a-b) 계산-0인지 확인 후 조건분기-YES 혹은 NO 출력으로 진행된다.

 

10101번: 삼각형 외우기(Bronze IV)

삼각형의 세 각의 크기가 주어지는데,  정삼각형/이등변삼각형/그냥 삼각형/삼각형이 아님을 각각 Equilateral/Isosceles/Scalene/Error로 구분하는 문제이다. 조건분기가 상당히 많아서 Bronze IV치고 더러운 축에 속하는데(물론 아희 유저의 관점에서), 코드는 다음과 같다.

카쿠
쿠방방싹방싼빠싿삭빠싿삳쟈숙처카삭빠싿산빠싿삳쟈숙처카사빠싿삭빠싿삳쟈숙처카
쿠ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ싸사파쏙ㅋㅋㅋㅋㅋㅋㅋ싼산파쏙ㅋㅋㅋㅋㅋㅋㅋ싸사파싹
사빠싿삭빠싿산빠싿삳다다밡발밭따따탸쿠차밝밡따밦다맣받반타밡따받다밡따밦다맣받반타밡따받다밡따밦다맣받반타밡따받다밡따받다맣받반타밡따받다밡따밦다맣바해
ㅋ부설커커커커커커커커커커커커커커커커
쿠사빠싿삭빠싿삳탸술차카삭빠싿산빠싿삳탸술차카
쿠ㅋㅋㅋㅋㅋㅋㅋㅋ받반타도ㅋㅋㅋㅋㅋㅋㅋ받반타다
살뺘붇처밡밡따반다맣받반타밡따반다밡따맣받반타밡따받반타다밡따밝다맣받반타밡따받다밡따맣받반타밡따반다밡따반다맣받반타밡따받다밡따반다맣받반타밡따반다밡따반다맣바해
투터번
뺘쿠처밣밡따받반타다맣받반타밡따받다밡따밝다맣받반타밡따받다밡따받다맣받반타밡따받다밡따밝다맣받반타밡따반다밡따맣받반타밡따반다밡따반다맣받반타밡따받다밡따맣받반타밡따반다밡따반다맣받반타밡따받다밡따밝다맣바해
ㅋ밝밡따밦다맣받반타밡따받다밡따발다맣받반타밡따밭다밡따맣받반타밡따반다밡따밦다맣받반타밡따받다밡따맣받반타밡따받반타다밡따밝다맣받반타밡따받다밡따밣다맣받반타밡따반다밡따반다맣받반타밡따받다밡따밦다맣받반타밡따받반타다밡따밝다맣받반타밡따받다밡따맣바해

코드가 굉장히 길긴 하지만, 출력 부분은 별로 볼 필요가 없으니 지우고 몇 가지 계산과 조건 분기가 일어나는 부분만 보도록 하자.

카쿠
쿠방방싹방싼빠싿삭빠싿삳쟈숙처카삭빠싿산빠싿삳쟈숙처카사빠싿삭빠싿삳쟈숙처카
쿠ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ싸사파쏙ㅋㅋㅋㅋㅋㅋㅋ싼산파쏙ㅋㅋㅋㅋㅋㅋㅋ싸사파싹
사빠싿삭빠싿산빠싿삳다다밡발밭따따탸쿠차Error
ㅋ부설커커커커커커커커커커커커커커커커
쿠사빠싿삭빠싿삳탸술차카삭빠싿산빠싿삳탸술차카
쿠ㅋㅋㅋㅋㅋㅋㅋㅋ받반타도ㅋㅋㅋㅋㅋㅋㅋ받반타다
살뺘붇처Scalene
투터번
뺘쿠처Isosceles
ㅋEquilateral

2~3번째 줄에서는 세 각도를 정렬하고 있다. 세 값을 각각 아, 악, 안에 저장한 뒤에 아>악이면 바꾸고, 악>안이면 바꾸고, 아>악이면 바꾼다. 이러면 아≤악≤안이 되도록 정렬된다.

4번째 줄에서는 아, 악, 안 스택의 값을 모두 앋 스택으로 옮겨서 더한 뒤 180을 빼서 0이 아니면 Error를 출력한다.

5~7번째 줄에서는 알 스택에 0을 넣고, 아=악이면 이것을 1 증가, 악=안이면 이것을 1 증가시킨다. 결과적으로 이 값이 2이면 정삼각형, 1이면 이등변삼각형, 0이면 모든 변의 길이가 다른 삼각형이 된다. 8~11번째 줄에서 이 조건 분기가 진행된다.

 

2752번: 세수정렬(Bronze IV)

숫자 3개가 주어지면 오름차순으로 정렬해서 출력하는 문제이다. 어? 삼각형 외울때 했네? 날로 먹어주자.

 

11401번: 이항 계수 3(Gold I)

사실상 Bronze 3개는 그리 어렵지 않았고, Gold 문제를 해결하는 것이 목표 성공 여부에 있어서 관건이었는데, 아희로 풀만 한 Gold 문제를 찾던 중 이 문제를 찾아서 도전하게 되었다. 4백만 이하(이후 서술의 편의를 위해 M을 4000000이라 두자)의 N, 0 이상 N 이하의 K가 주어질 때 \(_NC_K\)를 10억 7로 나눈 나머지를 출력하는 문제이다. N의 제한을 보면 O(N)에 풀라는 것 같은데, 일단 이항계수를 다음과 같이 나타낼 수 있음에 주목하자.

$$_NC_K=\frac{N(N-1)...(N-K+1)}{K!}$$

분자야 그냥 곱하면 되겠지만, 분모로 나누어 주어야 하는데 결과값은 정수이기 때문에 나눗셈에서 약간의 어려움이 있다. 하지만 간단한 발상의 전환을 통해 나눗셈 과정을 굉장히 간단하게 만들 수 있다. K는 M보다 작고, 결국 위 식에 M!을 곱하게 되면 식은 다음과 같이 바뀐다.

$$M!_NC_K=(N(N-1)...(N-K+1))((K+1)(K+2)...M)$$

즉, 우리는 우변의 정수를 구해준 뒤에 M!의 10억 7에 대한 잉여역수를 곱해주기만 하면 문제를 풀 수 있는 것이다. 이 과정을 수행하는 코드는 다음과 같다.

카쿠
쿠받반타밡따밦다밡따밡따받다밡따밦다밡따받반타다밡따밭다밡따밡따받반타다밡따밣다쌀발발다빠빠따따빠빠따따밠다싿받반타싹방빠방빠싼발발다빠빠따따반따빠따싼타
빠싹파빠싹탸쿠차삭싸받반타다빠싸따삳빠싹삭라사
순커커커머머석
빠쌀파빠쌀탸쿠차살싼빠받반타타싼따삳빠쌀살라산
뚜석썩뻐머머설
삳빠싹삭라망해

'카쿠/쿠'로 시작하는 구조는 내가 아희를 이용하여 문제들을 해결하면서 굉장히 애용하는 구조인데, 무엇이 장점이며 어떨 때, 어떤 방식으로 활용하는지는 다음 글에서 다뤄 보도록 하겠다.

 우선, 첫 두 줄은 필요한 값들을 저장하고, 입력을 받는 단계이다. 입력 전까지는 '알' 스택에 M!의 10억 7에 대한 잉여역수인 647658926을 넣고, '앋' 스택에 10억 7을 저장한다. 또한, '악' 스택에 1을 저장한다. 입력을 받고 둘째 줄이 끝난 뒤 '아', '안' 스택의 상태는 다음과 같다.

'아': N N-K

'안': K M

3번째 줄은 N(N-1)...(N-K+1)을 구하는 구간이다. '빠싹파빠싹탸쿠차'에서 '아' 스택에 있는 두 값을 '악' 스택으로 보내고, 둘이 같다면 반복문을 나온다. 그 후, '아' 스택에서 더 밑에 있던 값은 다시 '아' 스택으로 보내고(삭싸), 위에 있던 값은 1 증가시킨다(받반타다). 이를 복사하여 '아' 스택에 보낸 뒤(빠싸), '악' 스택에 있던 값에 곱하고(따), 10억 7로 나눈 나머지를 계산한다(삳빠싹삭라). '아' 스택에 처음 있던 N-K가 1씩 증가하여 N이 될 때까지 이 반복문이 진행되며, '악' 스택에 처음 넣어둔 1에 N-K+1부터 N까지 차례로 곱해진다. 반복문이 끝나면 '악' 스택에 있는 불필요한 두 값을 제거한다(머머석).

5번째 줄에서 하는 것 역시나 똑같다. 이번에는 '아', '악' 스택에서 '안', '알' 스택으로 바뀐 것 뿐이고, '안' 스택의 M값이 1씩 줄어들면서 '알' 스택에 있던 값에 M, M-1, ..., K+1이 곱해진다. 구조가 굉장히 비슷하기 때문에, 이 반복문은 위의 반복문과 비교해보면 쉽게 이해할 수 있을 것이다.

마지막으로 '악' 스택과 '알' 스택의 값을 곱하고(뚜석썩뻐), 10억 7로 나눈 나머지를 계산하여(삳빠싹삭라) 출력하고(망) 프로그램을 종료한다(해).

 

이렇게 나는 아희만을 이용하여 빼빼로를 만들었다. 귀찮음으로 인해 14달가량 지난 지금 글을 올리긴 하지만, 그래도 이 이벤트는 나에게 잊을 수 없는 하나의 사건으로 기억 될 것 같다.