결국 오고야 마는 것들

#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

c++의 ranged-based for문에 익숙해지니 이따금 c++이 선녀같아 보이는 마법에 빠졌다... #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; bool visited[10000]; int src, dst, t; void input() { fastio; cin >> t; } string bfs() { memset(visited, false, sizeof(visited)); queue q; visited[src] = true; q.push({src, ""}); while(!q.empty()) { auto [n, str] = q.front(); q.pop(); if(n == dst) return str;..

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

현재 아기 상어의 위치에서 먹을 수 있는 모든 물고기를 우큐에 넣고 맨 위를 먹으면 된다. 처음 아기 상어의 위치도 처리해주어야 한다. 오랜만에 구현 문제를 몇개 풀었는데, 미리 접근법을 충분히 구상하고 키보드를 잡으니 무난하게 풀렸다. 시간이 날 때 상어 시리즈도 혼내 줄 예정이다. #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}; pair babyShark; int sze = 2, cnt = 0; bool visited[20][20]; int arr[20][20]; int n; struct edible{ int ..

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