0과 1의 쉼터

문제Stanley is very prudent when it comes to his finances. He enjoys a somewhat spartan lifestyle and watches every penny he spends. Those few who call him friend view him as economical, abstemious, and parsimonious. He’s basically a miserly tightwad.Stan will never go shopping unless he has coupons. At the moment he has a bit of a conundrum. There are three items he wants to buy which have list c..

문제 7 3 8 8 1 0 2 7 4 44 5 2 6 5위 그림은 크기가 5인 정수 삼각형의 한 모습이다.맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.입력첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.출력첫째 줄에 합이 최대가..

문제Whoever wants to learn the game of golf has to cope with several oddities first (as with every other game that originates from Great Britain). One of them is the way to count the number of strokes a player needed to put his golf ball in a hole. There is a "par" for every hole, and practically all scores are expressed relative to the par. Examples are terms like "par", "birdie" (1 below par) an..

문제다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); }}fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.두 번째 호출한 fibon..

문제In this age of Internet, on-line connections, instantaneous email, etc., there are still some people who need to work with floppy disks. John is one of those. Every evening he goes home and continues what he has been doing in his office on his private UNIX system. He copies all the files he needs to floppy disks according to the following procedure:Put all files in one big SHAR file.Compress t..

문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.출력첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.둘째 줄에는 N을 1로 만드는 방법에 포함되어 있는 수를 공백으로 구분해서 순서대로 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.풀이아래 문제의 확장판이다. [백준 01463] 1로 만들기 [C/C++]문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으..

문제뿌요뿌요의 룰은 다음과 같다.필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된다.뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.남규는 최근 뿌요뿌요 게임에 푹 빠졌..

문제수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.입력첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.출력총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.풀이주어진 배열에 대한 구간 합을 구하는 문제다.최대 N = 1e5, M = 1e5 이므로 매번 구간 합을 구하면 시간초과가 발생한다. 부분합을 미리 구해주자.j번째 까지의 합에서 i - 1까지의 합을 빼야 한다. 출력 횟수가 많으므로 한번에 출력하자.소스코드보기출처https://www.acmicpc.net/problem..

문제2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.입력첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)출력첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.풀이dp[i] : 2xi 크기의 타일을 채우는 모든 경우의 수 n = 1 일때 1 : 2x1타일 1개로 채우는 방법n = 2 일때 2 : 2x1, 1x2 타일을 각각 2개로 채우는 방법n >= 3에 대해서는 점화식을 세울 수 있다.dp[i - 1]에 대해 2x1타일을 1개 붙이거나, dp[i - 2]에 대해 1x2 타일을 2개 붙이는 경우를 활용할 수 있다.이때, dp[i - 2]에 대해 ..

문제양의 정수 N의 디지털 루트를 구하려면 N을 이루고 있는 모든 자리수를 더해야 한다. 이때, 더한 값이 한 자리 숫자라면, 그 수가 N의 디지털 루트가 된다. 두 자리 이상 숫자인 경우에는 다시 그 수를 이루고 있는 모든 자리수를 더해야 하며, 한 자리 숫자가 될 때 까지 반복한다.24의 디지털 루트를 구해보자. 2+4=6이다. 6은 한 자리 숫자이기 때문에, 24의 디지털 루트는 6이 된다. 39의 경우에는 3+9=12이기 때문에, 한 번 더 더해야 한다. 따라서, 1+2=3이 디지털 루트가 된다.양의 정수 N이 주어졌을 때, 그 수의 디지털 루트를 구하는 프로그램을 작성하시오.입력한 줄에 하나씩 양의 정수가 주어진다. 입력의 마지막 줄은 0으로 나타낸다.  수는 최대 1000자리이다.출력입력으로 ..