0과 1의 쉼터

풀이 입력받은 지점사이의 거리(y-x)는 다음과 같은 규칙성이 존재한다. 거리의 제곱근의 정수를 기준으로 구간이 나뉜다. (ex : 3.0 ~ 3.xx, 4.0 ~ 4.xx), 제곱근의 정수를 n이라고 한다. 거리가 n*n 일때 작동 횟수는 2n - 1번이다. (빨간색) 거리가 n*n보다 크고, n*n + n 이하일 때 작동 횟수는 2n번이다. (초록색) 거리가 n*n + n보다 크고, (n+1)*(n+1)미만 일 때 작동 횟수는 2n + 1번이다. (파랑색) 거리 작동 횟수 이동 기록 1 1 1 2 2 11 3 3 111 4 3 121 5 4 1211 6 4 1221 7 5 12211 8 5 12221 9 5 12321 10 6 123211 11 6 123221 12 6 123321 13 7 12332..

풀이 666이 포함된 수가 나오는 순서와 입력된 값이 일치할 때 까지 수를 증가시키면 된다. 소스코드 #include int main(){ int N, cnt = 0, result, temp; scanf("%d", &N); for (result = 665; cnt < N;){ temp = ++result; while (temp) if (temp % 1000 == 666){ cnt++; break; }else temp /= 10; } printf("%d\n", result); } 출처 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 ww..

풀이 C로 풀기에는 난이도에 비해 번거로움이 많아 C++로 풀이했다. 기본적인 pop, push, empty, front를 사용하는 문제이기 때문에 C++에 이미 구현된 queue 라이브러리를 사용하면 된다. 순서(cnt)가 K로 나누었을 때 나머지가 존재하면, queue의 앞에있는 수를 제거하고, 뒤에 추가해준다. 아니라면, queue의 앞에있는 수를 출력해주고, pop하여, 마지막 요소인지 아닌지에 따라 출력 형식을 달리해준다. 소스코드 #include #include using namespace std; int main(){ int N, K, cnt = 1; cin >> N >> K; queue Q; for (int i = 1; i

풀이 좌표를 이용해 문제를 해결하기로 했다. N = 9일 때, N(9)/3의 패턴으로 둘러싸인 공백의 좌표는 (3, 3), (3, 4), (3, 5), (4, 3), (4, 4), (4, 5), (5, 3), (5, 4), (5, 5)이다. 이 좌표들은 N(9)/3으로 나누면, 1.xx인 점을 이용해 공백을 찍으면 된다. N(9)/3의 패턴 속의 공백들의 좌표는 (1, 1), (1, 4), (1, 7), (4, 1), (4, 4), (4, 7), (7, 1), (7, 4), (7, 7)이다. 이 좌표들은 "parameter로 받아오는 3으로 나누어진 N값"이 조건을 성립하지 않아 N = 1이 될 때까지 계속 재귀함수를 호출하며, 결국 조건을 성립해 공백을 찍으면 된다. 이외의 좌표들은 "parameter..

풀이 원래는 Brute Force로 해결하는 문제지만, 수의 범위가 작기 때문에 다음과 같이 풀이했. 1 ~ 99는 비교할 다음 자리의 수가 없기 때문에 한수이다. 백의자리 - 십의자리 = 십의자리 - 일의자리가 같으면 한수이다. 소스코드 #include int ap(int n){ int cnt = 0; for (int i = 1; i 0 && i < 100) cnt ++; else if (i/100 - (i%100)/10 == (i%100)/10 - ((i%100)%10)) cnt++; return cnt; } int main(){ int N; scanf("%d", &N); printf("%d", ap(N)); } 출처 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한..

풀이 생성자가 없으면, d(n)을 형성하지 못하므로, d(n)이 아닌 수들이 셀프 넘버라고 볼 수 있다. 소스코드 #include #define MAX 10001 int n_selfNum(int n){ int result = n; for (; n > 0; n /= 10) result += n%10; return result; } int main(){ int arr[MAX] = {0, }; for (int i = 1; i < MAX; i++){ int n = n_selfNum(i); n < MAX && (arr[n] = 1); } for (int i = 1; i < MAX; i++) !arr[i] && printf("%d\n", i); } 출처 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D..

풀이 "수 정렬하기 2"와는 반대로 시간효율보다 공간효율이 중시되는 문제이기 때문에 동일한 코드를 사용하면 틀릴 것 이다. 그래서, 주어지는 숫자의 개수를 배열에 저장 후, 각 숫자의 개수만큼 반복해서 출력하는 방법으로 해결했다. 소스코드 #include #define MAX 10000 int main(){ int N, num, cnt[MAX] = {0, }; scanf("%d", &N); while (N--){ scanf("%d", &num); cnt[num-1]++; } for (int i = 0; i < MAX; i++) if (cnt[i] != 0) for (int j = 0; j < cnt[i]; j++) printf("%d\n", i + 1); } 출처 10989번: 수 정렬하기 3 첫째 줄에..

풀이 입력받은 수 num이 num/2 이하의 범위 중에 소수가 존재하는지 몇 줄 내로 간단하게 해결할 수 있지만, 에라토스테네스의 체를 이용해 효율적으로 풀이해봤다. 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 구하는 알고리즘이다. N까지의 수는, N의 제곱근보다 작은 정수들의 배수를 모두 지우고 남는 수가 소수라는 사실을 알 수 있다. 이번 문제에서 주어지는 최대의 자연수는 1000으로, 1000의 제곱근인 31.62xxx보다 작은 정수 31까지의 배수들을 제외하고 남은 수들이 소수임을 알 수 있다. 하지만, 문제에서 입력받는 수가 소수인지 확인하기 위해 탐색하는 과정이 효율적이지 못해 위에서 조작한 배열을 소수와 소수가 아닌 구간으로 정렬해주었다. int arr[MAX], ..

풀이 좌표 정렬하기 1에서는 x를 우선으로 오름차순 정렬 후, x의 값이 동일할 때 y의 값으로 오름차순 정렬했지만, 이번 문제에서는 반대로 y를 오름차순 정렬 후, 동일값일때 x를 기준으로 오름차순 정렬하면 해결할 수 있다. 소스코드 #include #include typedef struct{ int x, y; }Point; int compare(const void *a, const void *b){ Point p1 = *(Point*)a, p2 = *(Point*)b; if (p1.y p2.y) return 1; else { if (p1.x p2.x) return 1; retu..

풀이 이분 탐색이란, 검색 범위를 줄여나가면서 원하는 데이터를 검색하는 알고리즘이다. 이를 사용하기 위해서는 요소들이 반드시 정렬되어 있어야 한다. N개의 정수를 Quick Sort로 정렬해준 후, M개의 정수를 입력받음과 동시에 Binary Search로 탐색해 해결했다. Binary Search의 Big-O는 O(log2n)이지만, n은 최대 100,000으로 재귀 함수로 구현해도 Stack Overflow가 발생하지 않기 때문에 재귀적/비재귀적 방법으로 둘 다 사용 가능하다. 소스코드 #include #include int compare(const void *a, const void *b){ int n1 = *(int *)a, n2 = *(int *)b; if (n1 < n2) return -1; ..