[ 해결 방법 ]기본적인 BFS문제인 것 같다. 현재 위치에서 위또는 아래 방향으로 BFS돌리면 된다. [ 내 코드 ]#include #include using namespace std; struct info{ int floor, cnt;};int F, S, G, U, D;int visit[1000002];int dir[2] = { 1, -1 };queue q; int main(){ cin >> F >> S >> G >> U >> D; dir[0] *= U; dir[1] *= D; q.push(info{ S, 1 }); visit[S] = 1; info cur, next; while (!q.empty()) { cur = q.front(); q.pop(); for (int i = 0; i F || next..
[ 풀이 방법 ]토큰이란걸 만들었다. 모든 토큰의 시작점은 트리의 단말노드이다. 토큰에는 현재 위치, 이전 위치, 총 이동거리의 정보를 포함하고 있다. 이 토큰을 큐에 넣고 하나씩 빼면서 현재 위치에서 이동할 수 있는 모든 방향으로 퍼지게 만들었다(BFS 방법). 이 때, 왔던 길로 다시 못가게 하기 위해서 토큰에 이전 위치를 저장했다. 이제 가려고하는 위치와 이전 위치가 같다면? 왔던길로 다시 돌아가는 거니까 못가게 막았다. 그리고 예외 상황이 문제를 짜증나게 만들었는데, 첫번째는 지름이 단말-단말 뿐만 아니라 단말-루트도 가능하다. 루트가 자식노드를 하나만 갖고 있으면 이런 경우가 가능하다. 두번째는 단말노드를 큐에 넣으면 안된다. 1만개쯤의 노드가 있다면 단말노드는 수천개쯤 된다. 메모리가 뻑날 수..
[ 해결 방법 ]점프를 할 수 있는 범위에서 제일 큰 돌의 좌표를 고르면 된다. 예를 들어 4칸을 뛸 수 있고 현재 위치는 첫번재 돌에 있다. 그리고 돌이 1, 2, 5, 7.. 순으로 있다면, 점프해서 최대로 갈 수 있는 위치는 4이지만 4에 돌이 없으므로 가장 가까운 2로가야한다. 다음엔 2에서 6까지 뛸 수 있지만 6에 돌이 없으므로 가장 가까운 5로간다. [ 코드 ]#include #define INF2000000000int T, tmpT;int pos[1000002];int main(){scanf("%d", &T);tmpT = T;while (tmpT--){int N, K;int pre, cur = 0, next, jmp = 0;scanf("%d", &N);for (int i = 1; i
[ 해결 방법 ]마지막 라운드에서 본인은 최고점을 받고 다른 사람들의 점수보다 크거나 같은지 판단하면된다. 이를 위해서, 우선 입력받은 점수를 오름차순으로 정렬한다. 현재 라운드까지 높은 점수를 받은 사람일 수록 마지막 라운드에서는 낮은 점수를 받아야한다.그래서, 현재 라운드 1등은 1점, 2등은 2점, 3등은 3점처럼 점수를 준다. 현재 라운드에서 자기보다 낮은 점수의 사람은 우승할 가능성이 없다. 자신이 최고의 점수를 받을 것이기 때문이다. 그러니 정렬한 배열에서 현재 인덱스보다 낮은 위치는 고려할 필요가 없다. 문제는 자기보다 높은 점수가 문제이다. 이 중에는 자신보다 높은 점수를 받는 사람이 있을 수 있다.이것을 해결하기 위해서, maxarr이라는 배열을 만들었다. 이 배열은 마지막 라운드 이후에..
https://www.codeground.org/main.do [ 해결방법 ] N이 10만이기 때문에 10만 X 10만의 배열을 선언해서 탐색하면 안된다. 메모리가 넘칠뿐만 아니라 제시간에 탐색할 수도 없다.대신, 좌표로 방번호를 구해야 한다. 좌표점을 가지고 어떻게 방번호를 알 수 있을까? 이 방의 탐색방향은 대각선이다. 예를 들면, (3, 1), (2, 2), (3, 1) 순서대로 탐색한다. 재미있는 것은 탐색방향이 바뀌기 전까지 x + y의 값이 같다는 것이다. 앞의 예에서는 x + y가 4로 모두 같다. 이점을 적극 활용해서 문제를 풀면된다. 우선, 탐색 방향이 바뀌는 점들을 모두 배열에 저장해 놓는다. N이 5일 때, 터닝포인트는 1, 2, 4, 7, 11, 16, 20, 23, 25이다. 다음..
https://www.acmicpc.net/problem/2293 [ 풀이 법 ] k원을 만드는 경우의 수는 아래의 그림과 같습니다. [ 그림 1. k원을 만드는 경우의 수 ] 우선, 위의 배열은 어떤 금액을 만드는 경우의 수입니다. 배열이름을 dp라고 하겠습니다. 그러면 dp(k)는 k원을 만드는 경우의 수입니다. 그리고 Cn은 n번째 동전의 가치입니다. 위의 예제 입력에서 C1은 1, C2는 2, C3은 5입니다. 그럼, 이런 식의 점화식이 가능합니다. dp( n, k ) = dp( n, k - Cn ) + dp( n - 1, k ) 이 점화식에서 dp( n, k )는 n개의 동전으로 k원을 만드는 경우의 수입니다. 그러므로 dp( n, k - Cn )은 n개의 동전으로 k - Cn을 만드는 경우의 ..
https://www.acmicpc.net/problem/10833 [ 문제 풀이 ]사과를 사람 수로 나눈 나머지를 다 더하면 된다. [ 코드 ] 12345678910111213141516#include int main(void) { int n; int student, apple, remain = 0; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d %d", &student, &apple); remain += (apple % student); } printf("%d\n", remain); return 0;}
https://www.acmicpc.net/problem/1932 [ 문제 풀이 법 ]다이나믹 프로그래밍은 bottom-up방식으로 밑에서 위로 올라가는 방식이다. 분할정복법과 대조된다.문제풀이법을 살펴보자. 임의의 원소까지의 최대값은 어떻게 될까? 위 예제에서 3행 2열의 값인 1을 임의의 원소로 잡고 여기까지의 최대값은 무엇일까? 최대값을 배열 DP에 저장한다.아마 대답을 이렇게 미룰 수 있을 것이다. 3행 2열을 오기 바로 전의 최대값 + 3행 2열의 값.의문은 3행 2열 바로 전까지의 최대값을 바로 알 수 가없다. 그런데, (1, 1)부터 시작하면, 최대값을 하나씩 쌓아갈 수 있다. 그래서 다이나믹 프로그래밍이 bottom-up방식의 문제해결법인 것이다.3행 2열 바로 전까지의 최대값의 후보는 2..
[10장. 64비트 모드로 전환하자.]를 읽다보니, kReadCPUID()함수를 어셈블리어로 작성했는데, 포인터를 다루더군요. 한번 정리할 필요가 있다고 생각되어 어셈블리어에서 포인터를 어떻게 다루는지 정리해보겠습니다. int main(){...DWORD dwEAX, dwEBX, dwECX, dwEDX; kReadCPUID(0x80000001, &dwEAX, &dwEBX, &dwECX, &dwEDX);..} 현재는 32비트 보호모드 상태이고, main문에서 CPU가 IA-32e모드를 지원하는지 알아보기 위한 함수(kReadCPUID)를 호출합니다.kReadCPUID는 어셈블리어로 작성되었습니다. 1 global kReadCPUID23 SECTION .text45 kReadCPUID:6 push ebp7 ..