본문 바로가기

분류 전체보기

 (308)
[백준/C++] 11052번: 카드 구매하기 문제https://www.acmicpc.net/problem/11052문제 요약민규는 N개의 카드를 구매하려고 한다. 카드는 카드팩 구매를 통해 얻을 수 있다. 카드팩의 종류는 N가지가 있다.- 1팩에 카드 1개가 있는 카드팩, 2개가 있는 카드팩, ... , N개가 있는 카드팩 카드가 i개 포함된 카드팩의 가격들이 주어졌을 때, 민규가 지불할 수 있는 금액의 최댓값을 출력한다.코드#include #include using namespace std;int N;// arr[i]: i개의 카드가 들어있는 카드팩의 가격int arr[1010];// dp[i]: i개의 카드를 구매하기 위해 필요한 최대 가격int dp[1010];int dfs(int cnt) { if (cnt == 1) return arr..
[백준/C++] 9020번: 골드바흐의 추측 문제https://www.acmicpc.net/problem/9020문제 요약골드바흐의 추측이란 유명한 정수론의 미해결 문제이다. 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다.이러한 수를 골드바흐 수라고 한다.또, 짝수를 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력한다. + 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우, 두 소수의 차이가 가장 작은 것을 출력한다.코드#include #include using namespace std;int T;// arr[i]가 true라면, i는 소수bool arr[10010];vector v;void gold(int n) { int left = 0; ..
[백준/C++] 1904번: 01타일 문제https://www.acmicpc.net/problem/1904문제 요약0 또는 1이 쓰여 있는 낱장의 타일이 있고, 타일들을 붙여 길이 n인 타일을 구성하려 한다. 이 때, 0이 쓰여 있는 타일은 하나를 사용할 수 없고 붙여서 00으로만 사용할 수 있다. 길이가 n인 타일 종류 개수를 출력한다.코드#include using namespace std;int n;int dp[1000010];int main() { // 입출력 단축 코드 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; dp[1] = 1; dp[2] = 2; for (int i = 3; i 코드 설명다이나믹 프로그래밍을..
[백준/C++] 18870번: 좌표 압축 문제https://www.acmicpc.net/problem/18870문제 요약수직선 위의 N개의 좌표 X1, X2, ... Xn이 주어질 때, 모두 좌표 압축을 적용하려고 한다. X를 좌표 압축하면, 수직선 위에 X보다 작은 좌표 수가 된다.(같은 값의 좌표가 여러 개일 경우, 1개로 생각한다.) 각 좌표에 압축을 적용한 결과를 출력한다.코드#include #include #include #include using namespace std;int n;int arr[1000010];vector v;int main() { // 입출력 단축 코드 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for..
[백준/C++] 1238번: 파티 문제https://www.acmicpc.net/problem/1238문제 요약N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. N명의 학생이 X번 마을에 모여서 파티를 벌이기로 했다. 마을 사이에는 총 m개의 단방향 도로들이 있고, i번째 길을 지나는데  일정 시간을 소비한다. 모든 학생이 파티에 참여하고 집으로 돌아오기로 했을 때,  가장 많은 시간을 소비하는 학생의 소요 시간을 출력한다.코드#include #include #include #include using namespace std;int N, M, X;vector> edges[1010];priority_queue> pq;// dist[i][j]: i에서 j로 갈 수 있는 최단 거리int dist[1010][1010];int di..
[백준/C++] 1074번: Z 문제https://www.acmicpc.net/problem/1074문제 요약2^N × 2^N 크기의 2차원 배열을 Z모양으로 탐색하려고 한다. N > 1인 경우, 배열을 크기가 2^(N-1) × 2^(N-1)로 4등분 한 후에 재귀적으로 탐색한다. N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력한다.  코드#include #include using namespace std;int N, r, c;int cnt;int res;void fillCount(int n, int x, int y) { if (x == r && y == c) { res = cnt; return; } else if (x > N >> r >> c; fillCount(pow(2, N..

티스토리툴바