https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 접근법 N 번째 피보나치 수를 구하는 함수를 실행했을 때 0과 1이 출력되는 횟수를 구하는 문제입니다. 문제를 풀기 위해 0과 1이 출력 되는 규칙을 찾아야 합니다. 0의 횟수와 1의 횟수가 피보나치 수를 이룬다는 규칙을 찾을수 있었습니다! 피보나치 수를 배열에 저장하고 이를 조건에 맞추어 출력해주면 문제를 해결할 수 있습니다. 아래는 코드입니다. 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 ..
https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 문제 접근법 n값이 5로 나누었을 때 나머지가 없다면 n 값을 5만큼 빼고 봉지의 갯수를 1개 늘립니다. n값이 5로 나누었을 때 나머지가 존재한다면 n 값은 3만큼 빼고 봉지의 갯수를 1개 늘립니다. 한번에 연산하지 않고 왜 나누어 연산을 하는지에 대한 의문이 들 수 있습니다. ex) 한번에 n / 5 개를 추가하면 안되는 이유(반례) : n이 16일 경우 5짜리 봉지 3개를 추가하면 1kg이 남습니다. ..
https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 주어진 조건에 맞게 구현을 하는 문제입니다. 주사위가 움직일 때 평면도의 어느부분이 어느곳으로 움직이는지를 신경써서 푸는 문제였습니다. 아래는 코드입니다. 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35..
www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제 접근법 S층에서 G층까지 가는 최소 버튼수를 구해야한다. 최단거리를 구할 때 사용할 수 있는 BFS를 사용해도 되는지 체크해본다. 최대 백만번을 초과하지 않으므로 BFS를 충분히 사용가능하다. 아래는 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42..
www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net 문제 접근 방법 S 지점부터 D값을 더하거나 빼서 동생들의 위치까지 가야한다. 어떻게 하면 최대값이 될까를 생각. (S - 동생들의 위치 값)들의 최대공약수를 구하면 그 값이 D값이 될것이라고 생각. 해당 생각을 코드로 옮김. 해당 문제에 대한 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ..
www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 접근법 땅의 크기와 이동 횟수가 몇번인지 생각해본다 땅의 크기 최대 50 * 50 = 2500 이동은 최대 2000번까지 단순 순회 가정이 5,000,000 DFS를 사용하여 땅을 순회하며 연합이 가능한지 체크한다. 연합을 한 땅끼리 값을 더 해준뒤 땅 갯수만큼 나누어서 분배한다. 이를 더 이상 연합이 생기지 않을 때 까지 반복한다. 아래는 코드입니다. 1 2 3 4 5 6 7 8 9 10 ..
https://www.acmicpc.net/problem/9019 9019번: DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경 www.acmicpc.net 문제 접근법 입력 값과 명령어를 저장할 queue를 만든다. 4가지 명령어를 수행할 때 방문을 체크하기 위하여 bool 값 배열을 준비한..
https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 문제 접근법 점화식을 세워 접근 하면 된다. 2xn의 직사각형이 있을 때 마지막에 1x2 타일이 없다고 가정하면 그 직사각형은 가로길이 n-1까지의 경우의 수 라고 볼 수 있다. 같은 경우로 2x1 짜리 타일이 없으면 가로길이 n-2까지의 경우의 수 라고 볼 수 있다. 단, 2x1 타일 대신 2x2 타일을 사용할 수도 있으므로 DP[N](2xn 까지의 경우의 수) = DP[N-1] + DP[N-2] * 2가 성립한다. 아래는 ..
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 접근법 점화식을 세워 접근 하면 된다. 2xn의 직사각형이 있을 때 마지막에 1x2 타일이 없다고 가정하면 그 직사각형은 가로길이 n-1까지의 경우의 수 라고 볼 수 있다. 같은 경우로 2x1 짜리 타일이 없으면 가로길이 n-2까지의 경우의 수 라고 볼 수 있다. DP[N](2xn 까지의 경우의 수) = DP[N-1] + DP[N-2]가 성립한다. 아래는 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 1..
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 접근법 제일 작은 수 부터 X까지 갈때의 경우의 수를 구한다. 해당하는 배열에 가장 작은 경우의 수를 넣는다. 아래는 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include #include using namespace std; int check[1000001]; int main() { check[1] = 0; int n; scanf("%d", &n); for (int i = 2; i
