일본 수학 올림피아드 2023년 예선 9번 문제인데, 올림피아드 치고는 생각보다 어렵지 않아서 가져와봄
고등학생 때 확통을 좀 했거나, 이건 예상이지만 아마도 프로그래밍 쪽 일을 하고 있다면 간단하게 풀 수 있을거라 생각함
다음은 풀이 예시
먼저 떠올릴 것은 절댓값을 거리라고 생각할 수 있다는 점임.
문제에서 주어진 상황을 생각해보면, 수직선 위에서 1부터 2023까지 모든 점을 한 번씩만 거치는 경로의 길이에 첫 번째 점과 마지막 점의 좌표를 더했다고 볼 수 있음.
그런데 이렇게 문제를 보면 영 깔끔한 맛이 없음. 그래서 다들 식을 변형해서 p1과 p2023을 묶어주면 예쁠 것 같다는 생각이 들거임.
이를 위해서 p0=0을 도입하고, p0을 두 개 빼주고 각각 p1과 p2023에 하나씩 붙인 후 절댓값으로 묶으면 abs(p1-p0), abs(p0-p2023)의 꼴이 나옴. 그러면 이제 식의 의미가 깔끔해지는데, 원점에서 시작해서 1부터 2023까지를 한 번씩 찍고 다시 원점으로 돌아올 때의 길이가 됨.
여기에서 우리는 좌변의 최솟값을 생각해볼 수 있음. 우변이 4048인데 0에서 2023을 한 번 찍고 돌아오려면 직선으로 달려도 4046이니까 조건을 만족하는 경로는 딱 1만큼만 가다가 반대 방향으로 꺾을 수 있음. 즉, 2023을 찍기 전이라면 10을 찍었다가 다시 8을 찍으면 8부터 10까지를 두 번 더 거치는데, 이러면 4046에 2*2가 더해져서 길이가 4050이 되니까 이런 순열은 불가능함.
딱 1만큼만 꺾을 수 있다는 건, 이 두 점을 묶을 수 있다는 뜻이 됨. 2023은 반환점 역할을 해야 하니까 제외하고, 1부터 2022 중에서 연속한 둘을 골라 묶으면 2021개가 됨. 이제 이 2021개 중 2023까지 갈 때 찍을 점을 적당히 고르고 나머지는 원점으로 돌아갈 때 찍을 점으로 쓰면 조건을 만족하니까, 그 경우의 수만 계산하면 문제는 해결. 묶인 두 개의 점은 갈 때 골랐으면 큰 거 먼저 찍고 작은 걸 찍고, 아니라면 작은 걸 먼저 찍으면 되겠지.
나는 중졸이었구나!
음 전혀모르겠어
머래 이 미친!!
나는 중졸이었구나!
머래 이 미친!!
아 완벽히 이해 했어(이해못함)
음 전혀모르겠어
그러니까 p1이 1, p2가 1, 2, p3가 1, 2, 3... 이런식으로 가는거지? p4-p3는 1, 2, 3, 4에서 1, 2, 3을 빼는거니까 4인거야?
p1부터 p2023까지 1부터 2023까지 중에서 수 하나씩을 배당하는 거임 내가 수학을 제대로 공부한 건 아니라 용어가 좀 헷갈리는데 수열이라고 생각하는 게 나을듯
p1=201, p2=374, p3=16 이런 식으로 간다고 보면 됨
아 그니까 순서 상관없이 중복되지만 않게 나열한다는 거지? 알겠음
아니다 이거 알고 봐도 모르겠다 ㅋㅋㅋㅋㅋ
원점에서 시작해서 1부터 2023까지 전부 한 번씩 찍도록 깡총깡총 뛴 다음 다시 원점으로 돌아올 때의 거리가 4048이 되도록 하는 경우의 수를 세는 문제인데 내가 설명을 못했나봐
자책하지마 유게이 그냥 내가 빡대갈이라서 그런거니까
전 오늘부터 중졸입니다
저는 초졸입니다.