본문 바로가기

백준30

[BOJ 9095] 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 1, 2, 3의 경우만 생각하여 풀면 된다. 4는 3 + [1], 2 + [2], 1 + [3] ([n]은 n을 만들 수 있는.. 2020. 1. 2.
[BOJ 2163] 초콜릿 자르기 https://www.acmicpc.net/problem/2163 2163번: 초콜릿 자르기 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 www.acmicpc.net N을 세로, M을 가로로 보았을 때 세로를 N-1번 잘라서 N개의 1 X M의 초콜릿을 얻고 1 X M을 M-1번 잘라서 1 X 1의.. 2020. 1. 2.
[BOJ 1788] 피보나치 수의 확장 https://www.acmicpc.net/problem/1788 1788번: 피보나치 수의 확장 첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 피보나치 수 F(n)에서 n이 음수의 경우에도 값을 구하는 문제이다. -1부터 F(n)을 구하다 보면 값의 절대값이 대칭이 되는 것을 볼 수 있다. F(n)이 음수인지, 양수인지, 0인지를 구하고 F(|n|)을 구하면 된다. #include unsigned long long F[1000001] = { 0 ,1 }; int main() { int n; scanf("%d.. 2020. 1. 1.
[BOJ 2407] 조합 https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 조합은 nCm = n-1Cm + n-1Cm-1 와 같은 특성을 가지고 있다. 이를 이용하여 nCm을 구할 수 있다. 하지만 n, m의 범위가 5 ~ 100이므로 unsigned long long로 배열을 구성해도 오버플로우가 발생한다. 이를 막기 위해서는 string을 이용하여 계산을 하거나, 자리수를 나누어 계산할 수 있다. 아래의 코드는 대략 앞 17자리, 뒤 17자리의 수를 저장할 구조체를 만들어 풀었다. #include #include const unsigned long long max = 1e17; ty.. 2020. 1. 1.
[BOJ 3054] 피터팬 프레임 https://www.acmicpc.net/problem/3054 3054번: 피터팬 프레임 문제 "피터팬 프레임"은 단어를 다이아몬드 형태로 장식하는 것이다. 알파벳 X를 피터팬 프레임으로 장식하면 다음과 같다. ..#.. .#.#. #.X.# .#.#. ..#.. "웬디 프레임"은 피터팬 프레임과 유사하지만, 다이아몬드를 '*'로 만드는 것이다. 알파벳 X를 웬디 프레임으로 장식하면 다음과 같다. ..*.. .*.*. *.X.* .*.*. ..*.. 단어가 주어졌을 때, 3의 배수 위치(세 번째, 여섯 번째, 아홉번째, ...)에 있는 알파 www.acmicpc.net "피터팬 프레임"은 '#'을 다이아몬드로, "웬디 프레임"은 '*"을 다이아몬드로 출력하는 모양이다. 두 모양 다 다이아몬드를 출력하.. 2019. 12. 30.
[BOJ 2960] 에라토스테네스의 체 https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 문제 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 www.acmicpc.net 2960번 문제는 2 ~ N까지의 수를 에라토스테네스의 체를 이용하여 지울 때 K번째 지워진 수를 찾는 문제이다. 간단하게 수.. 2019. 12. 30.
[BOJ 1629] 곱셈 https://www.acmicpc.net/problem/1629 불러오는 중입니다... 위 문제는 주어진 A, B, C에 대해 A^B % C를 구하는 문제이다. 간단하게 반복문을 B번 돌리면서 결과값에 A를 곱하고 C로 나눈 나머지를 구하면 될 거같은 문제이다. 바로 아래 코드처럼 말이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include #define ull unsigned long long int main() { int a,b,c; scanf("%d %d %d", &a,&b,&c); ull result = 1; for(int i = 0; i 2019. 3. 17.
[BOJ 1964] 오각형, 오각형, 오각형… https://www.acmicpc.net/problem/1964 1964번: 오각형, 오각형, 오각형… 첫째 줄에 N(1≤N≤10,000,000)이 주어진다. www.acmicpc.net 위 문제는 N단계 후 오각형의 점이 몇 개인지 알아내는 문제이다. 위 문제를 풀기 위해 저는 두 가지 방법으로 나누어 생각했습니다. ---------------------------------------------------------------------- 1). 외곽의 점은 몇 개인가 2). 그 외의 점들, 즉 안쪽에 있는 오각형의 점들은 몇 개인가. ---------------------------------------------------------------------- 1)번의 경우 각 단계마다 오각형의 각.. 2019. 3. 17.
[BOJ 1978] 소수 찾기 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 위 문제를 풀기 위해서는 '에라토스테네스의 체'를 알고 있다면 쉽게 풀 수 있다. 위 알고리즘을 통해 소수를 찾은 후 N개의 수를 입력 받으며 소수인지 아닌지 확인하면 된다. '에라토스테네스의 체'의 자세한 내용은 아래 URL을 통해 볼 수 있다. https://ladun.tistory.com/10?category=323065 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 .. 2019. 3. 16.

티스토리툴바