ABC175-C-풀이
Atcoder Beginner Contest 175 - C
문제해석
수직선에 사는 타카하시는 현재 X의 위치에 있다. 그는 D만큼의 거리를 음이나 양의 방향으로 정확히 K번 움직일 것이다.
더 정확하게 말하자면, 그는 한번 움직일 때, 좌표상에서 x의 위치에서 x+D 또는 x-D의 위치로 이동할 수 있다.
그는 K번 움직여서 위치한 좌표의 절댓값이 최소가 되도록 이동하고 싶다.
최소인 좌표의 절댓값을 찾아라.
문제설명
- 초기에 X에서 시작한다.
- x에 위치할때, x+D / x-D로 이동할 수 있다.
- K번 D만큼의 거리를 이동해야한다.
- X에서 시작해서 D만큼의 거리를 K번 이동하고 난 좌표의 절대값 중 최소가 되는 값(r)을 구하라.
제약 조건
- $-10^{15} \le X \le 10^{15}$
- $1 \le K \le 10^{15}$
- $1 \le D \le 10^{15}$
- 입력은 모두 정수
여기서 $10^{15}$크기의 값은 int로 해결할 수 없고 long long으로 처리해야 한다는 부분을 놓치면 틀리고 읭? 할수있다. (보닌 얘기..ㅠㅠ)입력
한줄에 X(시작위치) K(이동횟수) D(이동거리)가 주어진다.
X K D출력
X에서 시작해서 D만큼의 거리를 K번 이동하고 난 좌표의 절대값 중 최소가 되는 값(r)을 구하라.
r예시 및 설명
입력
6 2 4출력
2 - 6에서 4만큼 -의 방향으로 이동 -> 2
- 2에서 4만큼 -의 방향으로 이동 -> -2
- -2의 절댓값인 2 출력
풀이1
X가 양수인 경우
위 그림은 X부터 시작해서 D만큼 3번 움직인 그림
$X1 = X - D$
$X2 = X - 2D$
$X3 = X - 3D$
X로부터 D만큼 1,2,3번 좌측으로 이동한 경우, 위와 같은 형태를 띄게 됩니다.
X로부터 계속해서 D만큼 이동했을 때,
좌표의 절대값을 최소로 만들기 위해서 3번째 이동(X3) 이후부터는 X2와 X3을 번갈아서 위치해야한다.
X2에서 D만큼 양의 방향으로 이동하면 거리는 X1이 되고, $X2 + D$
X3에서 D만큼 음의 방향으로 이동하면 $X3 - D$
이렇게 0에서 더 멀어지기 때문이다.
현재위치(x)가 0보다 큰 경우, x에서 음의 방향으로 이동하고,
현재위치(x)가 0보다 작은 경우, x에서 양의 방향으로 이동한다. 현재위치(x)가 0과 같은경우는 절대값을 사용할것이기에 어느방향으로 이동하든 상관없다.
X가 음수인 경우, 0인 경우는 위에서 나온 결과를 토대로 확장할 수 있다.
현재위치(x)가 X와 같다고 하면, 아래와 같이 바꿀 수 있다. (x -> X)
현재위치(X)가 0보다 큰 경우, X에서 음의 방향으로 이동하고,
현재위치(X)가 0보다 작은 경우, X에서 양의 방향으로 이동한다. 현재위치(X)가 0과 같은경우는 절대값을 사용할것이기에 어느방향으로 이동하든 상관없다.
이 방법에서 문제는 $10^{15}$번 반복문을 돌리다보면 2초라도 당연히 시간초과~
풀이1 구현
long long x, k, d;
cin >> x >> k >> d;
while(k--){
if(x > 0) x -= d; // 현재위치(x)가 양수인 경우
else x += d; // 현재위치(x)가 음수거나, 0인 경우
}
cout << abs(x);
풀이2
1차원 좌표의 절대값은 0에서 좌표까지의 거리라고 할 수 있다.
X까지의 거리를 나타내보면
$X = D * n + r$ 으로 나타낼 수 있다.
r : 0에서 $X_n$까지의 거리
(수식 뜻 : X는 원점으로부터 D만큼 n번 이동한 만큼 + r만큼 떨어져있다)
n은 다음과 같이 구할 수 있다.
$n = quotinent(X, D)$ : X를 D로 나눈 몫
r은 다음과 같이 구할 수 있다.
$r = mod(X, D)$ : X를 D로 나눈 나머지
n과 대응되는 k를 비교해보면, 세가지 경우로 나눌 수 있다.
- k와 n이 같은경우
k와 n이 같으므로 k번 이동했을 때와 n번 이동했을때의 마지막 위치는 같게 된다.
따라서 결과는 r이 된다. - k가 n보다 작은 경우
k가 n보다 작다면 마지막 위치는 $x_k$가 된다.
따라서 결과는 X로부터 D만큼 k번 이동한 $x_k = X - d * k$가 된다. - k가 n보다 큰 경우
이때는 또 $n-k$가 짝수 / 홀수에 따라 나뉘게 된다. $x_n$의 위치에서 홀수번 더 이동하면 $x_n - d$의 위치로 가게되고,
$x_n$의 위치에서 짝수번 더 이동하면 $x_n$, 즉 제자리로 오게 되기 때문이다.
구현에서는 k와 n이 같은 경우와 k가 n보다 크고, k - n이 홀수인 경우를 합쳤음
여기까지 주의할 점
- X가 음수인 경우 절대값을 통해서 X를 양수로 바꿔줘야 한다.
D가 0인경우 X / D를 하면 0 나누기 오류(zero_division_error)가 발생하게 된다.-> d는 제약조건에 1보다 크거나 같다고 나와있다.
따라서 0인경우 n = 0, r = 0으로 처리해주면 된다.풀이2 구현
long long x, k, d; cin >> x >> k >> d; x = abs(x); long long n = x / d, r = x % d; if (n > k) cout << (x - k * d); // n > k의 경우 else if ((k - n) % 2) cout << abs(d - r); // k > n && (k - n) % 2 == 1 else cout << r; // (k == n) || (k > n && (k - n) % 2 == 0)다른사람의 풀이
https://atcoder.jp/contests/abc175/submissions/15918716 내 코드에서 사용한 변수명이랑 겹치게 코드를 약간 수정했다. ```cpp long long int x,k,d; scanf(“%lld%lld%lld”,&x,&k,&d); if(x<0) x*=-1;
long long int n = x/d; if(k<=n) printf(“%lld”,x-k*d); else { long long int r = x%d; if((k-n)%2==0) printf(“%lld”,r); else printf(“%lld”,d-r); } ```
음.. 똑같은 풀이로구만..
차이점은 10분만에 푸신 갓갓이랑..
저능 대회 끝나고 그 다음날 푼 벌레에오..
so gam
문제 많이 풀어봐야되고,
제약조건 잘 보자?
딱 요종도..
댓글남기기