0과 1의 쉼터

풀이 피보나치 수열과 같은 다음의 규칙이 존재한다. N 2진 수열 1 1 2 11 00 3 111 100 001 4 1111 0000 1100 1001 0011 5 11111 11100 11001 10011 00111 10000 00100 00001 Dynamic Programming 방식 중 Memoization 방식으로 풀이했다. 소스코드 #include int main(){ int N, dp[2] = {1, 2}, temp; scanf("%d", &N); if (N == 1){ printf("%d", 1); return 0; } for (int i = 3; i

풀이 "백준 1978 소수 찾기"문제와 유사하다. 단, 1은 소수가 아니다 arr[0] = 0으로 초기화해주자. 소스코드 #include #include #define MAX 1000000 int arr[MAX]; int main(){ int idx = 3; for (int i = 0; i < MAX; i++) arr[i] = i+1; for (int i = 2; i

풀이 다음과 같은 규칙이 존재한다. 둘째 줄부터 입력받은 수까지 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..

풀이 "백준 11053 가장 긴 증가하는 부분 수열" 문제와 동일하다. 소스코드 #include int main(){ int N, max = 0, length; scanf("%d", &N); int arr[N], dp[N]; for (int i = 0; i < N; i++){ scanf("%d", &arr[i]); length = 0; for (int j = 0; j < i; j++) if (arr[j] < arr[i]) length < dp[j] && (length = dp[j]); dp[i] = length + 1; max < dp[i] && (max = dp[i]); } printf("%d", max); } 출처 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어..

풀이 입력받은 지점사이의 거리(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에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 ..