여러분 안녕하세요
수학자 12번을 푼 원파입니다
정말 슬프네요
이 문제를 어려워하시는 분들을 보고
가르쳐드려야 할지
가르쳐드리지 말아야 할지
정말 난감합니다
꽤 못푸신 분들이 많더군요
정말 풀고 싶어하시는 것 같습니다
정말정말 선택의 고민이네요
그래서 크리스마스도 지났는데
선물을 안드렸으니 힌트글로 선물 드리겠습니다
순열 공부하신다고요... 허
순열은 그냥 여러 개 수가 있으면 이렇게 저렇게 배열해보는겁니다
예를 들어 1 2 3 이 있으면
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
이 1 2 3 의 순열이 되죠
즉 총 6가지입니다
이 6가지는 어떻게 나오냐!
첫번째 수는 1 2 3 중에 하나가 오겠죠
그러면 3가지가 있습니다
그리고 두번째는 첫번째에서 고른거 빼고 2가지입니다
마지막은 하나 남은 수를 배치하겠죠
즉 n개의 수의 순열의 개수는 n*(n-1)*...*1 이 됩니다
그리고 이것을 n! 이라고 쓰고 엔팩토리얼 이라고 읽을겁니다
순열은 배우고 뭐 할게 아닙니다 그냥 쉬워요
순열이 뭐다? 다 배열해보는거다!
간단하죠?
그러니까, 문제를 한번 살펴볼게요
길이가 20인 순열 어쩌구기호 {1, 2, 3, ..., 20}->{1, 2, 3, ..., 20}
이걸 더 쉽게 나타내면 이렇습니다
어떤 칸이 20개가 있는 수납함이 있어요
그리고 여러분은 1~20의 수가 적힌 숫자카드가 있어요
그리고 한 수납함마다 숫자카드 하나를 넣어요
그리고 나서 모든 수납함에 있는 카드의 수를 차레대로 읽어요
그러면 어떤 순열들이 나올까요
1 2 3 ... 20 도 나올테고
1 3 2 4 ... 20 도 나올테고
20 19 18...1 도 나오겠죠
네 이게 전부 어쩌구기호 순열이 될 수 있는 숫자의 나열입니다
그래서요
변수 i j를 잡습니다
어떻게 잡냐고요
i는 1보다 큰 값으로 잡고
j는 i보다 큰 값으로 잡고
대신 j는 20이하가 되게요
예를 들어 i=2 j=3도 되고 i=19 j=20도 됩니다
그 다음에는!
i j 잡은 다음에 뭐할까요
네 그렇죠
수납함의 i번째 칸에 있는 숫자 카드의 값을 봅니다 이걸 ㄱ이라고 불러요
j번째 칸의 카드도 보고 i-1번째도 봅니다 j는 ㄴ, i-1은 ㄷ이라고 불릅시다
i-1번째 수납함을 봐야 하니 i가 1보다 커야겠죠(i=1이면 0번째 수납함을 찾아야 하는데 그런건 없으니까요)
그 다음에는요
ㄱ은 ㄴ보다 작아야 되고 ㄴ은 ㄷ보다 작아야 돼요
i j가 여러개 잡히잖아요
위에서 예시를 든것처럼 i=2 j=3도 되고 i=19 j=20도 되니까요
그래서 ㄱ<ㄴ<ㄷ을 만족하는 i랑 j의 쌍을 다 찾아요
그리고 쌍의 개수를 ㄹ이라고 합시다
이때 ㄹ이 30이면, 총체적으로 답의 후보가 됩니다
뭐가? 순열이.
예를 들어서, 순열 (1, 2, 3, ... 20)의 ㄹ 값이 30이라고 쳐볼게요
그러면 (1, 2, 3...20)이 답의 후보가 되는 겁니다
그래서 답이 뭐냐! 후보의 개수입니다
그럼 여기까지 문제 이해와 순열에 대한 설명이었습니다
이해는 했는데 이제 어떻게 하냐 하시는 분들은 아래부터 보세요
리프님은 코드를 짠 실행하면 답이 뿅 나온다고 하셨는데요
저는 그게 어떻게 가능한지 잘 모르겠습니다
뭐 그건 그렇다고 치고
네
구글링
구글링도 할 줄 아는 사람이나 하는겁니다
그냥 문제 지문을 친다고 나오는게 아니죠
뭘 구글링해서 찾아야 할지 정확히 이해하는 사람만이
반드시 필요한 정보를 찾아내는 법입니다
뭘 찾아야 하는지도 모르는데 무턱대고
원파가 구글링이라 했으니까 구글링해야지
하시는게 아닙니다
첫 힌트글에서 말씀드렸다시피
제가 한 방법은 dp와 비슷하다고 했습니다
ps를 하신 분은 아실테지만 안 하시는 분들이 계시겠지요
dp의 기본 개념을 알려드릴테니 잘 적용해보세요
'문제를 쪼개세요'
네
이게 다에요
문제를 쪼개세요
어떻게 뭐로 쪼개냐고요
그건 푸는 사람의 몫이죠
제가 거기까지는 알려드릴 수가 없습니다
저도 해야 할 일들이 산더미같이 쌓여있으며
저도 미궁을 아직 풀고 있는 사람입니다
네..
문제를 쪼개세요
그 다음에는
문제를 쪼갠 것을 토대로
'코드' '코딩' '코딩으로 풀어야 된다' 같은거에 의존하지 마시고요
뭐 하실 수 있다면 하시는게 여러분의 손에 복을 선사하는 일이죠
안된다면
n이 작을 때를 손으로 순열을 해보면서 답을 직접 구해보세요
네
이건 진심입니다
여러분이 직접 해보세요
그리고 나서 구글링을 해보십시요
구글링을 가볍게 생각하시면 안됩니다
요즘은 인터넷만치면
세상 만사가 다 나오죠
그렇다고 세상 만사를 구글링에 바치시면 안됩니다
(무슨 뭘 가르치는게 되고 있는건지)
네
죄송합니다
말이 산으로 갔네요
그래서
제가 드리고자 하는 말은
무턱대고 구글링에 시간을 바치시지 말라는겁니다
어떻게 무엇을 찾을 것인지 정확히 이해하셔야 해요
정확히 이해가 되시면 풀이는 여러분께 다가올겁니다
구글링 또한 능력이지만
무얼 구글링할지 모르는 사람에게는 절대 도움이 되지 않음을 명심해주세요
그럼 이만 마지막 힌트를 남기며..
