본문 바로가기

분류 전체보기186

[C/C++] 백준 2775, Dynamic Programming 2775번: 부녀회장이 될테야 (acmicpc.net) 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net #include #include #include using namespace std; int compute(int k, int n) { int B[2][15]; int tod = 0; //현재층 (i-1층) int tom = 1; //다음 층 (i층) for (int i = 0; i 2022. 12. 10.
[C/C++] 백준 1463, Dynamic programming 1463번: 1로 만들기 (acmicpc.net) 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net * memoization이 아닌 recursive call을 사용하면 시간초과입니다. #include #include #include using namespace std; int min3(int a, int b, int c) { if (a < b && a < c) return a; else if (b < c) return b; else return c; } int make_one(int n) { vector arr(n + 1); int a = n; int b = n; int c = n; arr[1] = 0; for (int i.. 2022. 12. 10.
[C/C++] 백준 11047, Greedy 문제 11047번: 동전 0 (acmicpc.net) 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 코드1 #include #include #include #include using namespace std; int main() { int n, k; int t; int m = 0; vector arr, cnt; //arr:동전의 액면가, cnt: 동전의 개수 scanf("%d %d", &n, &k); for (int i = 0; i < n; i+.. 2022. 12. 10.
[C/C++] 백준 2839, Greedy 2839번: 설탕 배달 (acmicpc.net) 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net #include #include using namespace std; int main() { int n; int a, b; scanf("%d", &n); //2. a는 쓸 수 있는 최대 갯수의 5kg짜리 봉지의 수/ b=0 a = n / 5; b = 0; while (a >= 0) { //남은 무게: 전체 무게 - 5kg으로 만들 수 있는 무게 //n-5*a if ((n - 5 * a) % 3 == 0) { b = (n - .. 2022. 12. 10.
[C/C++] 백준 1012, DFS 1012번: 유기농 배추 (acmicpc.net) 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net strategy 1. connected component를 찾는 문제입니다 (1) cc_cnt라는 변수를 생성하여 connecte component를 탐색합니다 2. map[1000][1000]배열에 배추의 위치를 표시합니다 (1) 배추가 있는 곳=1 (2) 배추가 없는 곳=0 3. 배추A와 인접한 배추는 해당 배추A의 상, 하, 좌, 우에 위치한 것입니다 (1) 상, 하, 좌, 우는 x좌표 또는 y좌표에 1을 더하거나 뺀 .. 2022. 12. 9.
[C/C++] 백준 1260, DFS BFS 1260번: DFS와 BFS (acmicpc.net) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net #include #include #include #include #include using namespace std; vector edge[10001];//DFS와 BFS에서 같이 사용할 자료구조 int visit[10001];//DFS와 BFS에서 같이 사용할 자료구조 void initVisit(){//방문 기록을 0으로 초기화하는 함수 for(int i=0;i 2022. 12. 9.

티스토리툴바