URL : https://www.acmicpc.net/problem/10158 [ 문제 푸는 방법 ]처음엔 그림에서 처럼 개미가 경로를 따라가게 코드를 짰다. 경로를 한칸씩 따라가면 시간이 오래 걸리므로 부딪히는 바깥선을 계산했다.그런데 더 좋은 방법이 생각났다. 개미의 X, Y좌표를 분리해서 보니 재미있는 현상이 보였다. 개미가 움직이는 X좌표만 따로 떼어서 보면 개미는 X축을 왔다갔다 왕복한다.그래서 t초 후에 개미가 X축 위의 어디에 있을 지 생각하기 더 쉬워졌다. ( p + t ) / w값을 x라 하겠다. x의 의미는 개미가 p위치에서 t초동안 너비 w를 몇번 움직였는지 계산한 값이다. x값이 홀수이면, 개미는 x = w축에서 x = 0으로 가는 도중에 멈출 것이다. 반대로 x가 짝수이면, 개미는..
[ 해결 방법 ]1에서 n까지의 합은 아래 식과 같다. 이런 식이 어떻게 나왔는지 살펴보자. 예를 들어 6까지 수를 나타내면 다음과 같다. 1, 2, 3, 4, 5, 6 위의 수열의 합을 다음처럼 쉽게 생각할 수 있다. (1 + 6) + (2 + 5) + (3 + 4) = 7 + 7 + 7 = 21 위 식을 자세히 살펴보면, 괄호 안에 첫번째 값은 1씩 증가하고 두 번재 값은 1씩 감소하기 때문에 계속 값이 같은 것이다.이렇게 같은 합의 갯수가 n / 2개가 있다. 당연히 모든 수열을 두 개씩 짝지었기 때문이다.수열의 개수가 짝수개 일때 아래의 식이 만들어진다.그러면, 수열의 개수가 홀수 개일 때도 위 식이 성립할까? 1, 2, 3, 4, 5, 6, 7이 수열을 다음처럼 배치하자. (1 + 7) + (2..
[ 해결 방법 ]N을 몇 개 진행해보니까 피보니치 수열임을 알았다. 피보나치를 구현할 때 재귀로 구현하면 안된다. 이렇게 구현하면 불필요한 재귀를 호출하기 때문에 메모리 초과가 난다.fibo(10) fibo(9) fibo(8)fibo(8) fibo(7) fibo(7) fibo(6) 위에 그림처럼 fibo(8), fibo(7)을 이미 구했는데 불필요하게 호출한다. N이 커질 수록 이런 일은 더 많이 발생한다.생각해보면 피보나치는 fibo(n) = fibo(n-1) + fibo(n-2)이기 때문에 현재 값을 구하기 위해서 2개의 수만 알면된다. 이전값과 그 이전값. 그래서 변수 3개만 있으면 피보나치를 효율적으로 구현할 수 있다. 마지막으로 모듈러연산의 성질을 이용한다. 성질 1 : (a + b) % n =..
[ 해결 방법 ]점프를 할 수 있는 범위에서 제일 큰 돌의 좌표를 고르면 된다. 예를 들어 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/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;}