[일반] 지나가던 지잡대생인데 삼성 c형 어케풀어

[익명(223.38)]

b형은 은근좆밥이던데 c형은 샘플문제 손도 못대겠어

[0xrgb(0xrgb)]

ICPC 하는 입장에서는 C형 쉬움. 오히려 STL 못쓰게하는게 더 짜증났던것 같음

[0xrgb(0xrgb)]

그러니까 그냥 문제 많이 풀어보고, 몇몇 중요한 자료구조(e.g. BBST)는 STL 없이 짜는 연습 하는게 좋을것같음

[익명(223.38)]

샘플문제 풀이좀해줘 큐브맞추는거

[0xrgb(0xrgb)]

문제 퍼오는거 가능? 어디서보냐?

[익명(223.38)]

삼성 sw아카데미 가서 1770번 문제

[익명(223.38)]

아니면 힌트만 줘도되는데 이걸 전체를 다 검사하지 않고 다르게 하는방법

[0xrgb(0xrgb)]

아니 문제를 못찾겠어..

[익명(223.38)]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4szU-qXKYDFAUf&

[0xrgb(0xrgb)]

일단 Hopkraft carp 하나 떠오르네

[0xrgb(0xrgb)]

그런데 그렇게 복잡한거 안써도 풀릴거같긴함

[익명(223.38)]

삼성 b c형 다 어려운알고리즘이나 자료구조쓸필요 없지않아?

[0xrgb(0xrgb)]

그냥 3**16 짜리 배열이면 풀릴거같은데

[익명(223.38)]

거의 최적화아이디어랑 구현만 하면 되는거같던데

[0xrgb(0xrgb)]

삼성 BC형 어려운 알고리즘 요구하는거 거의 없음

[익명(223.38)]

b형도 나 할때 그리디응용이라 존나쉽게했는데

[익명(223.38)]

3^16이면 터지자너

[익명(223.38)]

안터지네

[0xrgb(0xrgb)]

3 ** 16도 아님. 그것보다 더 작은값이여도 됨

[0xrgb(0xrgb)]

아무튼 최적화 안하고 naive하게 풀어도 20초 제한이라 충분함

[0xrgb(0xrgb)]

풀어보지는 않았지만 1~2초안에 나오게 하는건 어렵지 않을듯

[0xrgb(0xrgb)]

이게 블럭이 int 크기만큼 들쭉날쭉 할줄 알았는데 그게 아니더만... 그러니까 쉬운 문제가 되는거지

[익명(223.38)]

naive하게 하면 아다리 맞는지 검사4*4 회전*4 n개n번 *30000^2

[0xrgb(0xrgb)]

그건 너무 naive하잖어 아다리 맞는지 체크를 int로 변환해서 한번에 하자

[0xrgb(0xrgb)]

굴곡이 +0 ~ +2 까지니까 3진법 수 16자리면 되겠네

[0xrgb(0xrgb)]

회전도 잘 생각해보면 위에 있을때랑 아래에 있을때의 모양을 한가지 형태로만 고정할 수 있음

[0xrgb(0xrgb)]

아무튼 힌트는 줄만큼 줬으니까 풀수있겠지? O(3**15 * 4) 정도로 풀면 될듯