본문 바로가기

문제풀이14

[BOJ 1932] 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 www.acmicpc.net 문제에서는 삼각형이 예각 삼각형처럼 보이지만, 입력을 보면 직각삼각형 형태이다. 이를 통해서 보면 i번째 줄에는 (i + 1)개의 입력.. 2020. 1. 13.
[BOJ 1924] 2007년 https://www.acmicpc.net/problem/1924 1924번: 2007년 첫째 줄에 빈 칸을 사이에 두고 x(1≤x≤12)와 y(1≤y≤31)이 주어진다. 참고로 2007년에는 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지, 2월은 28일까지 있다. www.acmicpc.net 입력받은 날짜까지의 일 수를 모두 더한 후 7로 나눈 나머지를 이용하여 요일을 출력하면 된다. #include int main() { int day[] = { 31,28,31,30,31,30,31,31,30,31,30,31 }; int m, d; scanf("%d %d", &m, &d); for (int i = 1; i < m; i++) d += day[i - 1]; s.. 2020. 1. 3.
[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.

티스토리툴바