결국 오고야 마는 것들

머리가 잘 안돌아가서 4번째까지 순서를 적어보니 규칙이 보였다. 1번에서 3번 장대로 원판 4개를 옮겨야 한다면 1번에서 2번으로 위의 3개 원판을 옮기고 가장 큰 원판을 1번에서 3번으로 옮긴 후, 2번에서 3번으로 다시 3개의 원판을 움직이면 된다. 이 과정을 n개에 대해서 수행하는 함수를 작성하면 된다. #include void moveN(int from, int to, int tmp, int n){ if(n == 1){ printf("%d %d\n", from, to); return ; } moveN(from, tmp, to, n-1); moveN(from, to, tmp, 1); moveN(tmp, to, from, n-1); } int main(){ int n, rep = 1; scanf("%..

혼내주기 2021. 8. 2. 00:07

#include #include using namespace std; using ll = long long; int map[100][100]; ll cache[100][100]; int n; ll bf(int x, int y){ if((x == n-1) && (y == n-1)) return 1; ll& ret = cache[x][y]; if(ret != -1) return ret; ret = 0; if(x + map[x][y] < n) ret += bf(x + map[x][y], y); if(y + map[x][y] < n) ret += bf(x, y + map[x][y]); return ret; } int main(){ ios::sync_with_stdio(0); cin.tie(0); memset(c..

혼내주기 2021. 8. 2. 00:07

문제 설명이 너무 귀엽다. ㅋㅋㅋㅋㅋㅋ 엄청난 초월번역. 다익스트라로 루피를 가장 적게 잃은 순으로 방문한적이 없는 동굴만 탐색하다 출구에 도착하면 종료하면 된다. #include #include #include using namespace std; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int map[125][125], visited[125][125]; int n; int d(){ priority_queue pq; pq.push({0, {0, 0}}); visited[0][0] = 0; while(!pq.empty()){ int cost = -pq.top().first, fx = pq.top().second.first, fy = pq.top()...

혼내주기 2021. 8. 2. 00:06

처음에 (operand operator operand)마다 계산해서 다시 스택에 넣는, 그래서 최종적으로 남아있는 스택의 원소가 답이 되는 방식으로 구현을 했는데, 괄호안에 식이 여러개 있는 경우를 처리하지 못해서 포기하고 방법을 좀 찾아봤다... operand들은 바로 결과에 넣고, operator들만 스택에 넣고 우선순위에 맞춰 스택을 비워주면 된다. 분명히 DS시간에 배웠던 기억이 어렴풋이 나는데 못풀어서 더 괴롭다... #include #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); string exp, ans; cin >> exp; stack s; for(auto c : exp){ if(..

혼내주기 2021. 8. 2. 00:05

스티커를 고르고, 재귀로 다음으로 선택 가능한 3가지의 스티커 중 점수가 가장 높은 스티커를 선택한다. 3가지의 스티커는 아래의 그림처럼 현재 스티커 다음 열의 대각선 스티커, 그리고 2열 후의 2개의 스티커이다. memoization 필수. #include #include #include #include using namespace std; int cache[2][100000]; vector v[2]; int n; int sticker(int x, int y){ if(y == n-1) return v[x][y]; else if(y == n-2) return v[x][y] + v[x == 0 ? 1 : 0][n-1]; int& ret = cache[x][y]; if(ret != -1) return ret..

혼내주기 2021. 8. 2. 00:04

그리디. 처음 플러그를 뽑은 우선순위를 1. 다시 사용되는 횟수가 적게 남은 플러그 2. 1번이 같다면 더 늦게 오는 플러그 이렇게 두고 풀었는데, 남은 횟수는 많지만 당장 사용되지 않는 탭들이 고여서 말썽이었다... 그래서 1. 다시 사용되지 않는 플러그 2. 가장 늦게 다시 쓰이는 플러그 이런 우선순위로 플러그를 제거해 해결했다. #include #include #include using namespace std; int tab[100], cnt[100]; int n; bool exist(int item){ for(int i = 0; i > n >> k; ..

혼내주기 2021. 8. 2. 00:04

문제는 매우 간단하다. 매번 토네이도가 이동할 때 마다 일정한 비율로 흩날리는 함수를 토네이도가 이동할 때 마다 불러주면 된다. 말은 쉽다... 아직 구현 문제가 익숙하지 않아서 시간을 많이 잡아먹었다. 공간지각능력이 부족해서 그런지 방향을 돌리는게 머리속에 그려지지가 않아서 아이패드에 그려놓고 돌리면서 좌표를 찍었다... #include using namespace std; int dx[4] = {0, 1, 0, -1}; int dy[4] = {-1, 0, 1, 0}; int d[4][2][9] = { { {-2, -1, -1, -1, 0, 1, 1, 1, 2}, {0, -1, 0, 1, -2, -1, 0, 1, 0,} }, { {0, 1, 0, -1, 2, 1, 0, -1, 0}, {-2, -1, -..

혼내주기 2021. 8. 2. 00:02

두 문제는 출력 형식만 다른 같은 문제다. 심지어 이름도 같다. 하나를 풀고 까먹을때쯤 다른 하나를 풀었어야 하는데, 눈앞에 꽁짜 경험치를 참지 못했다... 문제를 딱 읽었을 때 방법이 떠오르지 않아서 시간초과가 분명함에도 모든 정점에서 bfs를 돌렸다. 물론 시간초과. 도저히 떠오르지 않아서 좀 찾아보니 구사과님의 블로그에 트리의 지름을 구하는 잡기술이 있었다. 1. 트리에서 임의의 정점 u에서 가장 먼 정점 v를 찾는다. 2. 정점 v에서 가장 먼 정점 w를 찾는다. 정점 v와 w를 찾았다면 트리의 지름은 v와 w의 거리이다. 남은 부분을 뚝딱하면 문제 해결. #include #include #include using namespace std; vector adj[100001]; //vertex di..

혼내주기 2021. 8. 2. 00:02