카드 정렬하기 - 1715
파일 합치기 3 - 13975
N개의 묶음에서 묶음 단위 비교 횟수는 N-1번으로 고정되어있다.
결국 각각의 묶음들은 N-1번의 비교횟수를 나눠가진다고 생각해보자.
그러면, 개수가 적은 묶음이 비교를 많이할수록 개수가 많은 묶음들은 비교를 적게한다.
그리고 만약 개수가 X인 묶음이 있다고하자, 해당 묶음이 포함된 묶음을 N번비교한다면,
전체 비교횟수에서 N*X의 지분을 차지하게된다.
그렇다면, 개수가 적은 묶음을 비교해야 N*X의 값이 작아진다.
즉 개수가 적은 묶음을 먼저 비교해야한다.
단어 수학 - 1339
ABCDE는 A10000 + B1000 + C100 + D10 + E 이다.
알파벳에 곱해지는 수가 큰 항의 알파벳이 커야한다.
수 묶기 - 1744
수열의 점수 - 2036
minus * minus -> 더 커짐
minus * 0 -> 더 커짐
0 * 1 -> 더 작아짐
1 * plus -> 더 작아짐
plus(1제외) * plus(1제외) -> 더 커짐
PPAP - 16120
스택에서 앞에서부터 PPAP를 발견했을 때 무조건 P로 변경한다.
소트 - 1083
앞의 수가 제일 커지도록 한다.
앞에서부터 고려한다.
우체국 - 2142, 2285
(왼쪽에 있는 사람 + 현재 위치에 있는 사람) 수를 x명이라고 하자
오른쪽에 있는 사람 수를 y명이라고 하자.
왼쪽에서 오른쪽으로 이동한다면, 모든 사람과의 거리합은 y-x씩 줄어든다.
때문에 왼쪽에 있는 사람과 현재위치에 있는 사람이 오른쪽에있는 사람보다 적다면,
오른쪽으로 이동할때마다 모든사람과의 거리합은 줄어들것이다.
계속 이동하다가 거리합이 줄어들지 않는다면, 그 지점이 정답이 된다.
토너먼트 만들기 - 2262
f([선수목록]) : 각 시합에 임하는 두 선수의 랭킹 차이의 총 합의 최솟값
이라고 정의하자.
여기서 [1, 6, 2, 4, 3, 5] 선수들이 있다고 했을 때, 랭킹이 가장 낮은 6번선수는
어차피 경기를 한 번은 해야한다. 때문에 자신 바로 옆에 있는 선수 중 랭킹이 가장 낮은 선수와 시합해야한다.
왜냐하면 자신 바로 옆에 있는 선수가 먼저 시합한다면,
그 선수는 이기거나 질텐데, 이기면 그 선수와 시합하게되고 진다면 더 랭킹이 높은 선수와 시합해야하기 때문이다.
때문에 다음의 점화식이 성립한다.
f([1,6,2,4,3,5]) = f([1,2,4,3,5]) + abs(6-2)
결론은 랭킹이 가장 낮은 선수부터 랭킹차의 최소차를 더해주면 된다.
전생했더니 슬라임 연구자연던 건에 대하여 (Hard) - 14698
14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard)
작은 수와 작은 수를 곱해야 결과도 제일 작다
지뢰찾기 - 2140
지뢰가 있을 수 있는 곳은 무조건 있다고 한다.
문자열 생성 - 6137
뻔한 사전순
댄스 파티 - 2831
골드2(보석도둑, 컵라면)의 소재가 반영되었다. 골드 4라고 생각하지 않는다.
키큰 여자를 원하는 남자와 키작은 남자를 원하는 여자를 매칭시키는 경우를 생각해보자.
남자를 기준으로 생각했을 때, 키가 제일 작은 남자는 다른 남자들보다 원하는 여자의 수가 훨씬 많다.
하지만 키가 제일 큰 남자는 원하는 여자의 수가 훨씬 적을것이다.
때문에 키가 제일 작은 남자는 대체제가 많으므로
키가 제일 큰 남자부터 탐색한다. 그리고 남자 각각도 키가 큰 여자부터 탐색한다.
세 수, 두 M - 2405
두 편차의 차이가 커질수록, 중위값과 평균값은 멀어진다. 사실 평균의 의미로 찾았지만 수식으로도 증명가능하다.
| ((a+b+c)/3 - b) * 3 | = | a+b+c-3b | = | a-2b+c | = | (a-b) + (c-b) |
인데, (a-b)와 (c-b)는 서로 부호가 다르기 때문에, 두 값 차이가 커질수록 우리가 구하는 값은 커지는 것이다.
같은 수로 만들기 - 2374
스택으로 풀때 값을 하나씩 받아서 처리해서 스택이라고 분류한 것 같은데,
스택을 사용할 수는 있으나, 스택문제라고 보기는 어렵다.
오름차순이 이어질때는, 수의 차이만큼 카운트시킨다.
내림차순이 이어질때는, 무시해준다.
마지막에 내림차순이 이어진 후, 오름차순이 이어지지 않는다면 끝에서 Add연산이 이루어지지 않으므로
A의 max값에서 마지막값을 빼줘야한다.
콘센트 - 23843
물건을 쌓을 때를 생각해보자, 큰 물건부터 작은 물건들 까지 있을 때,
작은 물건부터 평평화 시키며 쌓으면 나중에 큰 물건이 왔을 때 윗면이 분명 울퉁불퉁할것이다.
즉, 큰 물건을 먼저 쌓고 작은 물건들로 조금씩 평평화 시켜야한다.
증명을 어떻게 해야하지는 잘 모르겠으나, 이 정도의 아이디어로 풀었다.
밥 - 23559
우선은 1000원의 메뉴로 모두 선택한다고 가정한다.
후에 4000원으로 구매할 수 있을 때까지, A로 변경했을 때 얻을 수 있는 맛이 더 클때까지 계속 변경한다.