-
[BOJ] 4243 : 보안 업체
4243 : 보안 업체 풀이 내가 지금 [left, right] 구간을 방문한 상태라고 하면, 다음 상태는 [left-1, right] 또는 [left, right+1]가 될 것이다. 이를 토대로 다이나믹 프로그래밍을 해주자. 단, 다음 두 상태로 나아갈 때 left에 서있는지 right에 서있는지에 따라 거리합이 달라지므로 이를 유의해서 코드를 짜보자. 코드 #include <cstdio> #include <cstring> typedef long long ll; int tc, n, s, a[102]; ll dp[2][102][102]; ll min(ll a, ll b) { return a<b?a:b; } ll dst(int x, int y) {...
-
[BOJ] 1713 : 후보 추천하기
1713 : 후보 추천하기 풀이 짜라는대로 짜면 된다. 코드 #include <cstdio> #include <deque> #include <algorithm> using namespace std; int n, m; struct abc { int idx, vote, time; bool operator <(abc a)const { if (vote == a.vote) return time < a.time; return vote < a.vote; } }; int main() { deque<abc> d; scanf("%d %d", &m, &n); for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); for (abc &it : d)...
-
[BOJ] 16120 : PPAP
16120 : PPAP 풀이 일반적인 괄호 문자열 문제랑 비슷하게 해결하면 된다. 코드 #include <cstdio> int t; char a[1000003], s[1000003]; int ppap() { if (t < 4) return 0; if (s[t-4]=='P'&&s[t-3]=='P'&&s[t-2]=='A'&&s[t-1]=='P') return 1; return 0; } int main() { scanf("%s", a); int cnt = 0; for (int i = 0; a[i]; i++) { s[t++] = a[i]; while (ppap()) t -= 4, s[t++] = 'P'; } puts(t == 1 && s[0] == 'P' ? "PPAP" : "NP");...
-
[BOJ] 16118 : 달빛 여우
16118 : 달빛 여우 풀이 다익스트라 짜면서 사람들이 많이 놓치는 부분이 있는데 if (dp[now] != current_sum) continue; 위와 같은 동작을 넣은 코드와 그렇지 않은 코드의 시간복잡도가 다르다. (자세히는 모름) 이 문제의 경우, 데이터가 엄청 빡세서 저 동작을 넣어주지 않으면 시간 초과를 받게 된다. 아래의 코드를 참고하자. 코드 #include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; typedef long long ll; int n, m; struct edg { int idx, cnt; ll dst; bool operator...
-
[BOJ] 16113 : 시그널
16113 : 시그널 풀이 잘 짜면 된다 코드 #include <cstdio> #include <cstring> int n, r[100003]; char a[100003], s[20005][5]; int isone(int x) { for (int i = 0; i < 5; i++) if (s[x][i] == '.' || s[x+1][i] == '#') return 0; return 1; } int count(int x) { int ret = 0; for (int i = x; i < x+3; i++) for (int j = 0; j < 5; j++) ret += s[i][j] == '.';...