분류 전체보기

(C++) 백준 1541번 - 잃어버린 괄호

문제 링크 : https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 풀이 그리디 알고리즘을 사용한 풀이이다. '-' 이후로 오는 수는 모두 빼기 처리해 주면 최솟값을 구할 수 있다. #include #include using namespace std; string raw, num; int result; int main() { cin >> raw; bool isMinus = false; for(int i = 0; i

(C++) 백준 11051번 - 이항 계수 2

문제 링크 : https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 문제 풀이 이항 계수의 성질 중 다음의 파스칼의 삼각형을 사용하여 풀었다. 처음에 재귀함수를 사용하여 풀이하였으나 그럼 시간 초과가 발생하기에 다음과 같이 dp로 풀이하였다. #include using namespace std; int n, k; int bicos[1005][1005]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; bicos[0][0] = bi..

(C++) 6064번 - 카잉 달력

문제 링크 : https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 문제 풀이 문제에 나온 예시를 들어보면 M = 10이고 N = 12일 때 첫 번째 해는 , 11번째 해는 , 13번째 해는 , 는 마지막인 60번째 해를 나타낸다. 이들의 규칙을 찾아보면 n번째 해는 임을 알 수 있다. 그리고 당연히 마지막 해는 규칙에 의해 최소공배수 즉 60번째 해임을 알 수 있다. 이를 이용하여 풀이하였다. #include using namespace std; in..

(C++) 백준 11653번 - 소인수분해

문제 링크 : https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 문제 풀이 소인수분해는 가장 작은 소수인 2부터 시작하여 합성수가 나눠지지 않을 때까지 계속해서 나눠주면 된다. #include using namespace std; int n; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(int i = 2; i*i

(C++) 백준 1929번 - 소수 구하기

문제 링크 : https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 풀이 에라토스테네스의 체를 사용한 풀이이다. #include #include using namespace std; int m, n; vector state(1000005, true); void prime(int n){ state[1] = false; for(int i = 2; i*i m >> n; prime(n); for(int i = m; i

(C++) 백준 1978번 - 소수 찾기

문제 링크 : https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 문제 풀이 만일 N이 2부터 √n의 수까지 나누어 떨어지는 경우가 있으면 이는 소수가 아니다. 이를 활용하여 풀이하였다. #include using namespace std; int A[102]; int n, cnt; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(int i = 0; i > A[i]; for(int i = 0; i < ..

(C++) 백준 1026번 - 보물

문제 링크 : https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 문제 풀이 그리디 알고리즘을 활용한 문제이다. 여러 수들의 곱의 최솟값을 구하고 싶다면 최댓값에 최솟값을 곱해주면 되고, 곱의 최댓값을 구하고 싶다면 최댓값끼리 곱해주면 된다. 그렇기에 우선 오름차순으로 정렬을 진행하고, 한 배열에선 값이 작은 앞의 원소를, 다른 배열에서는 값이 큰 뒤의 원소를 차례대로 곱하면 최솟값을 구할 수 있다. #include #include usin..

(C++) 백준 2217번 - 로프

문제 링크 : https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 문제 풀이 그리디 알고리즘을 활용한 문제이다. 최대 중량을 들기 위해선 더 무거운 중량을 들 수 있는 로프를 우선으로 사용해야 한다. 그렇기에 우선 오름차순으로 정렬을 진행하고, k개의 로프들을 사용해 봄으로써 들 수 있는 가장 높은 중량을 계산한다. #include #include using namespace std; int ropes[100005]; int n, mx; ..

(C++) 백준 1931번 - 회의실 배정

문제 링크 : https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 풀이 그리디 알고리즘을 활용한 문제이다. 회의실을 사용할 수 있는 회의의 개수를 최대로 하기 위해선 종료 시간이 가장 이른 순으로 사용하게 하면 된다. 그렇기에 회의가 종료되는 시간의 오름차순으로 정렬을 해놓고 시작 시간이 지나지 않은 가장 빠른 회의가 회의실을 사용하도록 하면 된다. #include #include #define X first #define Y second using namespace std; pair meetings[100005]; int n, cnt, cur, mn; bo..

(C++) 백준 11047번 - 동전 0

문제 링크 : https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 풀이 그리디 알고리즘을 활용한 문제이다. 가장 동전 수를 적게 이용하려면 금액이 큰 동전부터 빼가면서 계산해야 한다. 금액이 오름차순으로 입력되기 때문에 배열의 뒷부분부터 계산해 나가는 식으로 풀이하였다. #include using namespace std; int coins[12]; int n, k, cnt; i..