4,5 번 토론이나 힌트 부탁한다.
4번은 계속 0점 나오네
123은 만점이니 물어볼 사람 물어봐라
코드그라운드 끝났으니 물어보자
11111(122.44)
2015-11-14 21:02
추천 0
댓글 28
다른 게시글
-
코드쟁이들 ㅋㅋㅋㅋㅋ(112.159) | 15.11.14추천 0
-
족같은 내 머리 [3]ㅁㄴㅇㄹ(219.254) | 15.11.14추천 0
-
C 문자열 배열좀 알려주라 ㅜㅜ [4]qudtlsdlqs..(49.175) | 15.11.14추천 1
-
교보빌딩 뒤에서 계속 대치 중이다 [6]에어로홍(aerohong) | 15.11.14추천 1
-
컴퓨터랑 친해지고싶어서 프로그래밍배운다..dd(182.211) | 15.11.14추천 0
-
이것 좀 해석해주실분??개처럼일해..(thisiswhy) | 15.11.14추천 0
-
시발준벚(blossom1996) | 15.11.14추천 0
-
1만시간은 잠 안자면 1년만에 달성가능한데 [1](ㅇv ㅇ)(weaz86) | 15.11.14추천 0
-
(6일차) 오늘도 어김ㅇ벗이 돌아온 C++충 [2]ㅊㄹ(1.252) | 15.11.14추천 0
-
1만시간의법칙 프로그래밍도 통하냐? [4]익명(182.211) | 15.11.14추천 0
2 3번어캐함
3번 dp?
문제가 뭥미?
ㄱㅆㅇ) 1번 혹시 공유 가능하냐 내방법틀린거 같은데
1번 gcd, 2번 dp, 3번 dp, 4번 segment tree, 5번 시간복잡도 m^2 + nm log n에 짰음.
3번 dfs로 했는데 점수 ㅅㅂ 풀이좀 올려줘
2번은 흔히하는 베스킨라빈스 게임 도입해서 바로 풀었다
ㅅㅂ 나도 베스킨라빈스 했는데 왜 75점이냐
나도 베스킨라빈스 생각해서 햇는데 잘안되던데 ㅅㅂ
2번 알고리즘. a가 이기는것만생각하믄 된다. 31부르면 진다고 하면 30부르면 이기자나 그러믄 a가 2명이고 k가 3이면 최소 2~최대6을 부르ㅡㄹ수 있는거. 그상황에서 b최소 b최대 계산하면 a최소+b최대 ~ a최대+b최소 의 경우는 무조건 a가 b가 무슨짓을 하건 만들수 있으니까 각각 케이스마다 a가 처음에 부를 수 있는 수 범위안에 있는지 계산하면 됨. 예를들어 베스킨라빈스 31은 a=1,b=1,k=3인경우니까 1+3 즉 4를 무슨짓을 하건 부를 수 있음 30mod4=2니까 2부르면 이김 이런식
내가생각한게 너랑 거의똑같은데 한가지 놓친게있네 왜 a가 이기는것만 생각하면됨?? 난여기서 막혀서 건들지도못했는데.. a가이기는거랑b가이기는거랑 구별이 안돼
3번은 존나 쉽다. 각각 케이스 (i,j에서의 케이스) 마다 왼쪽에서 올 경우 오른쪽에서 올경우를 계산하는데 그거를 생수별로 최소값만 저장하면서 쭉 올라가면 된다. 즉 3차원 배열에서 마지막 차원이 생수고 전생수가 1이고 이번 생수가 있으면 생수하나 추가해주면서 데이터 쓰고 그러면 졸라쉬움
11111 그렇게했는데 75점이던데. 코딩실순가
a가 이길수 있는 모든경우에서 안되면 b가이기는거임. 조건에서 반드시 누군가 이기는지 알 수 있다고 했으니깐.
흠..이해가안가는군 시바 빠가인가 ㅠㅠ
아마 75점이면 케이스 한가지만 했을꺼임. 4를 무슨짓을 하든 부를수 있는경우는 a,b가 둘가 1일경우임 이게 a,b가 숫자가 2이상되면 그게 범위가 됨 예를들어 4~6은 무조껀 만들수 있다 이런식으로. 테스트 케이스에서 2번째꺼가 9~11이었던거로 기억함. 그 범위를 모두 생각해야함.
4,5번 푼 형님들 안계시나 댓글 말고 따로 글써서 올려주셔도 됨.
4번 시작점 순으로 소팅하고 끝점이 큰 값에서 작은 값 순으로 최장길이수열 구하면됨
5번 floyd 로 품. 1차때 냈던거 복붙해서 코드 5줄추가해서 냈더니 300뜨던데.. floyd 적용하면 딱히 어려운 적용이나 응용없이 바로풀림.
4번은 dynamic programming 에서 유명한 knapsack 푸는 방식으로품
근데 위 방법이 훨씬 쉬워보인다. 내가 ㄹㅇ헛짓을 했구나...ㅜㅜㅜㅜㅜ공부더하고 내년을 노려야지...
4번 sorting + labeling + longest decrease sequences 로 품.... 몇점 까지가 본선 행일까 ㅠ
4번 LIS, 5번 다익스트라 + 역추적
LIS로도 가능하군...
아니 N이 10만인데 LIS가 가능함?
5번 다익스트라로 했는데 왜 시간 부족하다고 하냐
LIS 내가 잘못 알고 있었네.. nlogn이라니.. ㅂㄷㅂㄷ..
5번 시간복잡도 잘못 계산했네. O(nm log n)인듯. 그냥 dijkstra n번 돌려서 역추적하면 됩니다. floyd 돌려도 상관 없지만, dijkstra n번 수행하는게 훨씬 빨라요.