결국 오고야 마는 것들

우큐를 두개 만들고 값과 index를 넣는다. D 연산의 경우 해당 인덱스가 유효하지 않다고 표시해 반대 우큐에서도 거르면 된다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; int t, n; void input() { fastio; cin >> t; } int main() { input(); int num; char s; while(t--) { cin >> n; priority_queue minHeap; priority_queue maxHeap; vector valid(n, true); int cnt = 0; for(int i = 0; i > s >> num; if(s ==..

혼내주기 2021. 8. 1. 22:30

종만북으로 한창 공부할 때 힘들게 풀었었는데, 다시 풀어도 마냥 쉽지는 않은 문제. dp를 이용해 중복 계산이 없도록 하면서 모든 순서대로 계산한 결과의 최솟값을 재귀적으로 찾으면 된다. 11066 파일 합치기 문제와 아주 유사하다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; int arr[500][2], cache[500][500]; int n; void input() { fastio; cin >> n; for(int i = 0; i > arr[i][0] >> arr[i][1]; } int min(int a, int b) {return a > b ? b : a;} int df..

혼내주기 2021. 8. 1. 22:29

#include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); long long n, Hatk, t, a, h; long long Hmaxhp = 0, ans = 0; cin >> n >> Hatk; for(int i = 0; i > t >> a >> h; if(t == 1){ //싸움 if(h % Hatk == 0) Hmaxhp += a * ((h/Hatk) - 1); else Hmaxhp += a * (h/Hatk); } if(t == 2){ Hatk += a; Hmaxhp -= h; if(Hmaxhp < 0) Hmaxhp = 0; } ans = max(ans, Hmaxhp); } cout

혼내주기 2021. 7. 26. 22:43

처음에 생각없이 플로이드로 풀었다가 TLE. 두번째로 m값이 생각보다 작아서 다익스트라를 n번 돌려서 풀었는데, 고수들의 코드를 보니 정방향 역방향으로 한번씩만 돌리면 풀리는걸 보고 한 수 배웠다. 아마 m값이 100000이었으면 내 무식한 방법은 또 TLE였겠지... #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; vector adj[1001]; vector rev[1001]; int arr[1001], dist[1001]; int n, m, x; void input() { fastio; cin >> n >> m >> x; int a, b, c; for(int i = 1; i > a >> b >> c; ad..

혼내주기 2021. 7. 26. 22:42

공기에 노출된 부분을 bfs로 구하고, 그 정보를 이용해 치즈를 녹인다. 이 과정을 치즈가 전부 녹아내릴때 까지 반복하면 된다. 근데 진짜 치즈 내부에는 구멍이 있어도 상관없나?? #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; bool arr[101][101], exposed[101][101]; int n, m; void input() { fastio; cin >> n >> m; for(int i = 0; i > arr[i][j]; } i..

혼내주기 2021. 7. 26. 22:42

다익스트라의 경로를 출력하는 문제. 경로가 갱신될 때 마다 어느 위치에서 왔는지 저장해둔 뒤, 다익스트라가 끝나면 도착점 부터 시작점까지 스택에 경로를 넣고 하나씩 꺼내면서 출력하면 된다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; vector adj[1001]; int n, m, src, dst; void input() { fastio; cin >> n >> m; int a, b, c; for(int i = 0; i > a >> b >> c; adj[a].push_back({c, b}); } cin >> src >> dst; } void dijkstra() { vector..

혼내주기 2021. 7. 26. 22:42

adjacency matrix로 1 -> 2 -> 3 순서라면 아래와 같이 모든 순서를 표현한 뒤 1 -> 2 1 -> 3 2 -> 3 등수가 바뀐 순서만 적용해서 위상정렬을 하면 된다. 문제를 풀면서 아쉬웠던 점: 계산을 잘못해서 adj matrix로 바로 넘어가지 못함 아무리 생각해도 ?인 경우가 없는데, 문제에 써있다고 나를 의심함 => 낚임 이 문제를 풀면서 아직도 내가 키보드를 너무 일찍 잡는다는걸 느꼈다. 경우의 수와 complexity 계산을 정확히 하는 능력도 아직 부족하다... #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; bool adj[501][501]; int rnk[501], ind[..

혼내주기 2021. 7. 26. 22:42

소문의 테트로미노... 최대한 무식하지 않게 짜려고 노력했다. 5개의 도형 원형을 만들고, 대칭과 회전으로 생기는 경우의 수를 모두 모아서 하나의 배열에 저장한 뒤, brute force로 최대값을 찾는다. 푸는데 시간이 꽤나 걸렸다. 배열 돌리기를 연습하면 푸는 시간을 단축할 수 있을까? #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; vector tetrominos; int arr[505][505]; int n, m; void input() { fastio; cin >> n >> m; for(int i = 0; i > arr..

혼내주기 2021. 7. 26. 22:42