PS
-
새벽에 끝내는 scpc 2024C&E: career & experience/Contest 2024. 7. 8. 08:45
입시가 끝났다... 본인은 이제 응애 학부 1학년생이다.학부생이라면 반드시 해봐야 하는 것 중 하나가 있다면 바도 ps대회이다. 진짜로.ucpc와 scpc를 모두 나갈려고 했으나 귀찮은 관계로 생략, scpc만 신청했다. (대회 마지막날에 신청한 건 비밀) 토요일 기자단발대식 + 월요일 마감 통계학 과제 + 일요일 미팅이 있어서 시간이 좀 부족할 수도 있겠다 싶었는데 오히려 시간은 널널했다. koi처럼 시간으로 변별하는 느낌은 아닌 듯.뭐 그냥 예선도 아니고 예선 1차라서 오후에 두 분메 새벽에 두 분제 풀고 5번문제는 쿨하게 때려치고 잤다. round1_01.c더보기#include #include #define max(a, b) (((a)>(b))?(a):(b))int Fnc(char f){ ret..
-
백준 3015번 오아시스 재결합 (boj/3015.c)R&E: research & education/PS 2024. 1. 15. 11:16
조금 새로운 이진탐색 문제입니다. 직관적으로는 스택을 사용해서 풀 수 있지만 그렇게 풀면 시간복잡도가 N^2이 되버리므로 나락을 가버립니다. 스택에 들어가는 값이 항상 정렬되있다는 사실을 활용, 이진탐색으로 시간복잡도를 NlogN까지 올릴 수 있습니다. #include int stk[500000] = { 0, }; int srcs(int val, int sze){ int lft=0, rht=sze-1, mid; for(mid=(lft+rht)/2;lft
-
백준 2618번 경찰차 (boj/2618.c)R&E: research & education/PS 2024. 1. 14. 13:42
DP문제입니다. 공간복잡도 O(W^2), 시간복잡도 O(W^2)으로 해결가능합니다. 또한 각 사건마다 할당된 경찰관을 묻고 있기 때문에 간단한 자취 남기기 기법을 응용합니다. DP의 구성은 아래와 같습니다. 회색 영역은 초기화 때 계산됩니다. 빗금 영역에 있는 값 중 최소의 값을 문제의 답으로 결정합니다. 한 번에 계산되는 양은 아래와 같습니다. 코드는 아래와 같습니다. #include #include #define SZE 1000 int dp[SZE+1][SZE+1]; int idx[SZE+1][2]; int giv[SZE+1] = { 0, }; typedef struct _p{ int row; int col; }point; point loc[SZE+1]; int get_dst(point p1, poi..