백준 1011번/ Fly me to the Alpha Centauri [C]
해당 카테고리에 봉인한 x64 asm로 작성한 hello world를 뒤로하고 첫 프로그래밍 글을 적어보려고 합니다
CTF 문제 풀 때만큼이나(?) 재미있는 문제라고 느끼면서 푼 것 같습니다.
C언어 코드로 작성하였고 그나마 C를 사람처럼 함
메모리도 적게 쓴 것 같아 기분이 좋네요 헿
해당 문제는 저희가 우현의 우주선을 Alpha 뭐로 보낼 때의 최소 이동 횟수를 구하는 문제인데요
문제까지 글로 쓰긴 엄마가 강아지 산책시키라고 해서 문제를 모르신다면 한 번 읽어보시는 것도...ㅋㅋ
문제에 따라 1의 거리, 2의 거리.... 20의 거리(?) 뭐 몇 거리나 하나 생각해보면 (특징을 위해 5부터 예로)
| X | Y | 위프 | 최소 거리 |
| 0 | 5 | 1211 | 4 |
| 0 | 6 | 1221 | 4 |
| 0 | 7 | 12211 | 5 |
| 0 | 8 | 12221 | 5 |
| 0 | 9 | 12321 | 5 |
| 0 | 10 | 123211 | 6 |
| 0 | 11 | 123221 | 6 |
| 0 | 12 | 123321 | 6 |
| 0 | 13 | 1233211 | 7 |
정신없이 적어서 맞을지는 모르겠지만 맞을 겁니다
처음에 문제를 접했을 때 이거 뭔가 피라미드처럼 허허.. 망했구먼 싶었는데
사실 이문제의 핵심은 N에서 -1, 0, +1로만 이동할 수 있다는 것과 마지막의 거리는 1이라는 것인데요
이 문제는 물론 여러 풀이 방식이 존재하지만 저는 해당 워프(?)를 조금 변경해서 문제를 풀었습니다
| 1211 |
| 1221 |
| 12121 |
| 12221 |
| 12321 |
| 123121 |
| 123221 |
| 123321 |
| 1231321 |
강조한 부분만 보시면 감을 잡으시는 분들이 많을 거라 생각합니다(이해 못해도 상관없습니다)
위프를 보면 왼쪽 오른쪽으로 값이 증가하는 것을 알 수 있는데요
이는 결국 처음과 끝의 속도는 1 이여야 하기 때문이죠
즉 왼쪽 증가 --> 오른쪽 증가 --> 왼쪽 증가 --> 오른쪽 증가.... 반복
코드로 작성해보면
while (y > 0) {
y = y - left; // 왼쪽 빼줌
x++;
if (y <= 0) { // 검사
break;
}
y = y - right; // 오른쪽 빼줌
x++;
left++;
right++;
}
printf("%d\n", x);그러면 도착하는 값을 왼쪽으론 쪽을 반복해서 거리와 빼주는 과정을 반복하면 답이 최소거리가 나오겠죠
그럼 이런 의문점이 생깁니다
???: 야 그럼 123121은 거리가 음수가 되는데?
어...
결국 음수가 나오지 않는 경우는 결과가 0이겠고 그러기 위해서는 왼쪽과 오른쪽의 수가 같은 경수가 되겠죠
크게 생각할 필요가 없는데 결국 남은 마지막 수는 최고 거리보다 수가 적을 것이고 나중에 그것을 검사하나 지금 음수가 되는 것까지 검사하나 증가 값은 동일하게 1이라는 점입니다.
해당 부분은 제가 글로 설명하기 어려움이 있는 것 같아 코드랑 워프 표랑 비교해 가지고 실행도 시켜보고 디버깅도 해보시면서 하면 이해하는데 더욱 좋을 것 같습니다
이젠 진짜 강아지 산책시켜야 돼서 빠르게 코드 적고 나가보겠습니닿ㅎㅎ
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {
int T = 0;
int x = 0, y = 0;
int left = 0, right = 0;
scanf("%d", &T);
for (int i = 0; i < T; i++) {
scanf("%d %d", &x, &y);
y = y - x;
x = 0;
left = 1;
right = 1;
while (y > 0) {
y = y - left; // 왼쪽 빼줌
x++;
if (y <= 0) { // 검사
break;
}
y = y - right; // 오른쪽 빼줌
x++;
left++;
right++;
}
printf("%d\n", x);
}
}
수정해야 될 부분이나 틀린 부분 지적할 부분 있으시면 꼭 말씀해주세요