0과 1의 쉼터

풀이 다음과 같은 규칙이 존재한다. 둘째 줄부터 입력받은 수까지 push를 해주어야 하며, push는 이전에 입력된 수보다 큰 수가 입력될 때만 발생한다. push가 발생하거나, 이전에 입력된 수보다 작은 수가 입력될 경우 불필요해 생략한 후 pop가 발생해야한다. 만약, pop이 발생하지 않았다면, 스택을 이용해 수열을 만들 수 없다는 의미이다. 따라서, 둘째 줄부터 입력받는 n개의 수들을 저장할 필요가 없다. 소스코드 #include int main(){ int n; scanf("%d", &n); int stack[n], top = 0, val, idx = 0, num = 0; char op[2*n]; for (int i = 0; i < n; i++){ scanf("%d", &val); for (in..

풀이 입력받은 지점사이의 거리(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..

소스코드 #include int main(){ char ch; while (scanf("%c", &ch) != EOF) putchar(ch); } 출처 11718번: 그대로 출력하기 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄은 주어지지 않는다. 또, 각 줄은 공백으로 시 www.acmicpc.net

풀이 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..

풀이 시간제한이 있어 규칙을 찾아 단순 연산으로 풀이해야 하는 문제이다. A만큼 올라갔을 때, V이상이면 멈추고, 그렇지 않으면 B만큼 감소한다. (A-B가 V-B 이상) (V-B) / (A-B)의 값이 위 조건을 성립하지만(소수점 단위를 포함한 최소조건), 날짜(정수)를 기준으로 며칠이 걸리는지 구해야 하기 때문에 다음과 같이 식을 변경했다. 1 + (V-B-1) / (A-B) 소스코드 #include int main(){ int A, B, V; scanf("%d %d %d", &A, &B, &V); printf("%d\n", 1+(V-B-1)/(A-B)); } 출처 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,..

풀이 5kg 봉지를 최대한 많이 들때, 배달하는 봉지의 개수가 최소인점을 이용해 풀이했다. 입력받은 N을 5(kg)로 나누었을 때 나머지가 0이면 몫이 봉지의 개수이다. 나머지가 0이 아니라면, 몫(cnt)을 한 개씩 줄이고, 3(kg)봉지를 몇개를 추가해야 알맞게 배달할 수 있는지 계산한다. 만약, 나누어 떨어지지 않는다면 cnt는 -1로 감소하며, -1을 출력할 것이다. 소스코드 #include int main() { int N, cnt = 0; scanf("%d", &N); cnt = N / 5; if (N % 5) for (; cnt >= 0; cnt--) if ((N - 5 * cnt) % 3 == 0) { cnt += (N - 5*cnt) / 3; break; } printf("%d\n", c..

풀이 힌트를 보면 쉽게 이해할 수 있다. 단, long long 데이터 형식의 범위를 초과하는 것을 방지하기 위해 중간 계산과정에서 MOD로 나눈 나머지를 저장했다. 소스코드 #include #define MOD 1234567891 int main(){ char str[51]; long long result = 0, r = 1; int L; scanf("%d %s", &L, str); for (int i = 0; i < L; i++){ result = (result + (str[i]-'a'+1) * r) % MOD; r = (r*31) % MOD; } printf("%lld", result); } 출처 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 ..

풀이 층, 호를 입력받을 때마다 거주민을 구하는 방식보다는, 처음부터 모든 층, 호의 거주민을 구하는 방법이 효율적이다. k층 1호는 항상 1명이 거주한다. 0층 n호는 n명 거주한다. k층 n호의 거주민은 k층 n-1호, k-1층 n호 거주민의 합과 동일하다. 소스코드 #include #define F 15 #define NO 14 int main(){ int T, k, n, arr[F][NO]; for (int i = 0; i < F; i++) for (int j = 0; j < NO; j++) arr[i][j] = ((i&&j) ? arr[i][j-1] + arr[i-1][j] : (i?0:i)+j+1); scanf("%d", &T); while (T--){ scanf("%d %d", &k, &n)..

풀이 4673 - 셀프 넘버 문제와 비슷하다. 단, 생성자의 여부가 아닌, 가장 작은 생성자를 출력해야 한다. 생정자의 범위는 N - 자리수 * 9 부터 N-1이다. 만약 생성자를 구하지 못했다면, 0을 반환한다. 소스코드 #include int selfNum(int n){ int cnt = 0, temp = n; for (; temp > 0; temp /= 10) ++cnt; for (int i = n - 9*cnt; i 0; temp /= 10) result += temp%10; if (result == n) return i; } return 0; } int main(){ int N; scanf("%d", &N..

풀이 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