본문 바로가기

분류 전체보기

 (386)
[c++] 백준 2232 분해합 백준 단계별로 풀어보기 [브루트 포스] 분해합 https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net [풀이] 245의 분해합은 245+2+4+5 = 256. 반대로 256의 생성자는 245가 된다. 생성자는 여러개일 수도, 없을 수도 있다. 1 0) std::cout
[c++] 백준 7568 덩치 백준 단계별로 풀어보기 [브루트 포스] 덩치 https://www.acmicpc.net/problem/7568' 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net [풀이] 몸무게를 배열 x에, 키를 배열 y에 저장한다. 본인보다 몸무게와 키가 모두 큰 경우에만 덩치가 큰 것으로 인정해 count 값을 증가시키고 count + 1인 자신의 등수를 배열 level에 저장한다. [코드] #include int main() { int n, count; std::cin >> n; int* x = new in..
[c++] 백준 1085 직사각형에서 탈출 백준 단계별로 풀어보기 [기본수학 2] 직사각형에서 탈출 https://www.acmicpc.net/problem/1085 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형의 왼쪽 아래 꼭짓점은 (0, 0)에 있고, 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] x, y, w-x, h-y 중 가장 min 값을 구하면 된다. [코드] #include int main() { int x, y, w, h; std::cin >> x >> y >> w >> h; w -= x; h -= y; x = x >= w ? w : x; y = y >= h ? h : y; std::cout = y ?..
[c++] 백준 4948 베르트랑 공준 백준 단계별로 풀어보기 [기본수학 2] 베르트랑 공준 https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net [풀이] 이전에 했던 소수 판정식을 이용해서 풀면 시간초과가 나온다. 따라서 에라토스테네스의 체라는 소수판별에 최적화된 알고리즘을 이용하여 풀어야 했다. 에라토스테네스의 체는 소수를 판별할 범위까지 배열을 만든 다음, 특정 수의 배수에 해당하는 수를 계속 지워나가는 방법이다. 이때 자기자신은 제외하고 이미 지워진 수는 건너뛴다. [코드]..
[c++] 백준 2581 소수 백준 단계별로 풀어보기 [기본수학 2] 소수 https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net [풀이] 소수는 1과 자기자신으로만 나누어지는 수. 따라서 2~m/2까지의 수에 대하여 나누어떨어지는 수가 있으면 소수가 아니다. [코드] #include int main() { int m, n, sum = 0; std::cin >> m; std::cin >> n; int least = 10001, check = 1; if (m == 1) m++; for (; m
[c++] 백준 1712 손익분기점 백준 단계별로 풀어보기 [기본수학 1] 손익분기점 https://www.acmicpc.net/problem/1712 1712번: 손익분기점 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 www.acmicpc.net [풀이] 고정비용 A, 가변비용 B, 가격 C에 대해서 손익분기점이 발생하려면 A + B * 생산대수 = C인 경우 손익분기점이 존재하지 않고, 존재한다면 ( A / ( C - B ) ) + 1이 된다. [코드] #include int main() { int ..
[c++] 백준 10872 팩토리얼 백준 단계별로 풀어보기 [재귀] 팩토리얼 https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net [풀이] 팩토리얼을 재귀로 푸는 방식이야 매우 단순하고, TMP로 짠 코드에 대해서만 잠깐 복습하겠다. C++에서는 타입에 값을 부여해서 그 타입들을 가지고 연산을 할 수 있는데, 타입은 반드시 컴파일 타임에 확정되어야 한다. 따라서 컴파일 타임에 생성되는 코드로 프로그래밍을 하는 것을 메타 프로그래밍이라고 한다. 템플릿 메타 프로그래밍(TMP)를 이용해서 재귀적 구조를 나타낼 수 있다. 이때 N=1인 베이스 케이스는 템플릿 특수화를 이용해 처리한다. [코드]..
[c++] 백준 2839 설탕 배달 백준 단계별로 풀어보기 [기본수학 1] 설탕 배달 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net [풀이] n = 3*a + 5*b 이므로, 가능한 a+b의 최솟값을 구한다. a가 3과 곱해지므로 n = 3*a + 5*b를 만족하는 경우가 더 있더라도 count 값은 최소가 아니다. 따라서 n이 나누어떨어지면 바로 루프를 탈출하고, 만약 count 값이 a+b로 바뀌지 않고 여전히 0이면 정확히 나누어떨어지지 않으므로 -1을 출력한다. [코드] #incl..

티스토리툴바