오랜만에 하니까 다까먹어서 존나뒤적거리네 앰ㅋㅋ
핵심 로직은 다 짠거같은데
프로그래밍 이야기: sort
- dc official Cpp
아 시발 stl뒤져ㅋㅋㅋ
17번(wjd918273)
2020-07-27 22:40
추천 0
댓글 59
다른 게시글
-
프로그래머에게 돈쓰는 호갱님들 많지않냐익명(175.113) | 20.07.27추천 1
-
좀 잘하려고 하는새끼들은익명(183.101) | 20.07.27추천 0
-
언리얼 엔진이 c언어맞냐? [1]익명(39.7) | 20.07.27추천 2
-
ai나오기전까지는 거지로 살게?익명(110.70) | 20.07.27추천 0
-
파이썬 책 추천좀익명(112.121) | 20.07.27추천 0
-
와치독스하면서 하는말인데 실제로 해킹해서 TV화면 주작하는게 가능하냐? [1]익명(39.7) | 20.07.27추천 1
-
백엔드도 공룡책 봐야함?익명(121.140) | 20.07.27추천 0
-
네트워크 책 이거국룰아니었음? [5]익명(121.141) | 20.07.27추천 0
-
플러터 쓰는 스타트업 병특 가고 싶다 크크 [1]익명(61.77) | 20.07.27추천 0
-
개발자가 리눅스자격증있으면 좋은점뭐임익명(175.113) | 20.07.27추천 0
....... 씹천재 - dc App
내 코드 어디가 틀렸는지 봐줄 수 있음? - dc App
??어디올렸노... 근데 내가 생각하고있는 풀이 아직 구현못해서 시간 만족하는질 모르겠음ㅋㅋㅋㅋ - dc Cpp
난 포기함. 유파로 최소길이 구하고 - dc App
유니온 파인드 써본적없어서 모르겠는데 내가 생각한거나 대충 이야기해보고 자러갈까싶음 - dc Cpp
최소인덱스는 길이 아니깐 따로 구함... - dc App
어캐 했음? - dc App
일단 통나무를 자를 수 있는 곳이 K개고, 다 자른다고 치면 K+1개가 나올거임. 이걸 배열 1번에 저장하고, 1번째부터 K번째까지, i번째 통나무와 i + 1번째 통나무를 합쳤을 때의 길이를 배열2에 저장함. 이 배열2의 길이는 K겠지? 그럼 이제 K배열에서 가장 작은 값을 찾아서, 해당 인덱스(자르는 부분과 연관되어있음)를 매개로 - dc Cpp
배열1에 접근해서 해당부분을 이어붙임. 이 때 K번째 통나무에 K + 1번째 통나무의 길이를 더하고, K + 1번째는 -1로 세팅해줌 - dc Cpp
이런식으로 짧은걸 계속 이어붙여가면, -1로 이어붙인곳이라는 표시가 남으니, 반대로 마지막에 -1이 아닌놈은 잘린곳이라는 뜻임 - dc Cpp
그래서 -1이 아닌 가장 앞선 인덱스를 반환하고, 그 값들중 가장 큰 값은 최대 통나무 길이가 될것임 - dc Cpp
이어붙이는건 당연히 K-C에 연관있음. 등호 여부는 대충 하시고 ㅎ - dc Cpp
5 4 2 1 2 3 4 - dc App
5 4 1 - dc App
그게 무슨숫자들이냐 - dc Cpp
그런식으로 하면 합쳤을때 젤 작은 길이 같은 거 있으면 어떡함. 이거 때문에 첫 인덱스 한방에 못구함 - dc App
당연히 같은숫자있으면 뒤(오른쪽) 우선이디 - dc Cpp
테케 나무길이 5고 1 2 3 4 에서 자를수 있을 때 2번만 자르는걸로 해보셈 1 3 잘라야 함 - dc App
ㅇㅇ 뒤쪽하면 그리디 안해서 1 3 안나옴 - dc App
나무길이 5고, 1 2 3 4가 자를수있는 부분인거지? - dc Cpp
그러면 토막은 1 1 1 1 1이 되잖아? 그럼 맨 뒤거부터 합쳐. 1 1 1 2. 그다음 또 1 2 2가 되겠지. 답은 2잖아 - dc Cpp
슈도코드로 쓰는게 낫나 - dc Cpp
1 2 2 ㅋㅋㅋㅋ - dc App
방금 말한건 통나무 길이임ㅇㅇ - dc Cpp
나도임. 1 2 2 도 되니깐 ㅇㅇ 첫인덱스 1 임 - dc App
아 시바 머지 - dc App
그러면 배열1엔 1 2 -1 2 -1 들어가게됨. 이중 가장 큰값은 2이고, 1, (2 -1), (2 -1) 세토막나있다는걸 알수있음 - dc Cpp
아 머꼬 암튼 3번합치기 ㄱ. 1번 자르는건가 - dc App
흠..양수를 뒤로미는게 더 편하겠다. 1 (-1 2) (-1 2) - dc Cpp
1뒤쪽 인덱스 1, 2 뒤쪽 인덱스 3, 2 뒤쪽 인덱스 5. 여기서 5는 무시....긴 한데 어차피 1만 필요하고. - dc Cpp
1번 짜르는건 어캐됨? 뒤에서부터 합치면 3에서 짜르는거 아니냐 - dc App
일단 1 2 3 4 5 있잖아. 다 잘랐다고 가정하고 이어붙이는데 뒤부터 이어붙여 - dc Cpp
그럼 1 2 3 (45) 이렇게 되잖아. 길이는 1 1 1 2인 상태고 - dc Cpp
그럼 이어붙일걸 또 찾는데, 찾는 방법은 미리 저장해둔 배열에서 인접 합이 가장 작은놈을 찾는거임. - dc Cpp
1 2 2 -> 3 2 - dc App
1 (2) 1 (2) 1 (3) 2 여기서 괄호안은 인접 요소들의 합이고, 이중 가장 작은건 2이고, 그중 가장 오른쪽걸 취한다. - dc Cpp
그럼 중간의 (2)를 취하는거겠지, 합치면 1 2 2가 되는거임. ㅇㅋ? - dc Cpp
한번 더 합치면 3 2 라고 ㅇㅇ - dc App
처음에 '배열2'를 언급했을 때 말했듯, 괄호안의 숫자는 미리 계산해둠. 물론 합치는 과정에서 업데이트 해줘야함 - dc Cpp
합치면서 숫자가 C + 1개 남으면 멈춰야지. - dc Cpp
최소합 찾아서 합치는건 유파로 해도되서 알겠는데 - dc App
C가 2였고 그럼 숫자가 3개 남을때까지 반복해야함 - dc Cpp
5 4 1 요 - dc App
한번만 가르는거니깐 3번 합쳐야 하잖아 - dc App
음? 5 4 2인줄. 무튼. - dc Cpp
아 뭔말하는지 이제이해했네 - dc Cpp
그니깐 3 2 되서 첫 인덱스 못구함 - dc App
ㅇㅇ글네. 그건 좀더 생각해봐야할 부분이구만 - dc Cpp
뭐 그리디 안되면 dp도 시도해봐야지ㅋㅋ - dc Cpp
여튼 출근해야되니까 잔당ㅎㅎ - dc Cpp
근데 최소 길이 알면 O(K^2) 에 첫인덱스 구할 수 있음 - dc App
문젤 얕보긴 했다잉... 뭐 나보다 코테 더 많이 연습한거같은데 ㅋㅋ나보다 잘 하것지 - dc Cpp
시작인덱스 정해서 거기부터 시작해서 토막길이가 Len보다 크지않게 최대한 길게 잡으면서 C-1번 해서 L넘는지 보면됨 - dc App
뭔가 깔쌈한 답이 있을거라고 믿어의심치 않음... 내일 출퇴근길에 또 생각해보겠삼... 도합 4시간이니까는... - dc Cpp
내 유파 풀이 2800바이트인데 ainta는 800바이트임... - dc App
유저이름인가? 무튼 엄청 길게나올문제는 아닐거같음ㅇㅇ - dc Cpp
국대 - dc App
그렇구만 - dc Cpp
근데 L이 무지막지하게 긴게, 파라메트릭인줄 알았는데 - dc App