분류 전체보기 (308) 썸네일형 리스트형 [백준/C++] 25602번: 캔 주기 문제https://www.acmicpc.net/problem/25602문제 요약랑이 집사는 매일 고양이 랑이와 메리에게 캔을 하나씩 준다. 랑이 집사는 N가지 종류의 캔을 갖고 있고, i번째 캔을 A[i]개 갖고 있다. 랑이와 메리는 입맛이 까다롭고 변덕이 심해서 매일 각 캔에 대한 만족도가 다르다. 랑이가 i번째날 j번째 캔을 먹었을 때, 만족도는 R[i][j]이다. 메리가 i번째날 j번째 캔을 먹었을 때, 만족도는 M[i][j]이다. K일 동안, 랑이와 메리에게 캔을 주었을 때, 만족도 합의 최대를 출력한다. 코드#include #include #include #define ll long longusing namespace std;int N, K;// A[i]: i번째 캔 개수int A[10];// .. [백준/C++] 2529번: 부등호 문제https://www.acmicpc.net/problem/2529문제 요약두 종류의 부등호 기호 ''가 k개 나열된 순서열 A를 입력 받는다. 해당 부등호 기호들 앞뒤에 서로 다른 한 자릿수 숫자를 넣어 모든 부등호 관계를 만족시켜야 한다. 이 상황에서 부등호 기호를 제거한 뒤, 숫자를 붙이면 만들어지는 수들 중 최대 최소를 각각 출력한다.코드#include #include #include #define MAX_K 10using namespace std;// 부등호 개수int k;// 부등호 순서열char A[MAX_K];string max_num = "0";string min_num = "9876543210";bool visited[MAX_K]; void dfs(int num, string s) {.. [백준/C++] 14889번: 스타트와 링크 문제https://www.acmicpc.net/problem/14889문제 요약n명의 사람을 절반으로 나누어 스타트 팀과 링크 팀을 만든다. S[i][j]는 i번 사람과 j번 사람이 같은 팀에 속해 있을 때, 팀에 더해지는 능력치이다.(S[i][j]와 S[j][i]는 다를 수 있다.) n과 S[i][j]가 모두 주어졌을 때, 스타트 팀과 링크 팀의 능력치 차이의 최솟값을 출력한다.코드#include #include #define MAX_N 20using namespace std;int n;int S[MAX_N][MAX_N];// 최소 차이int res = 1e9;// i번 사람이 선택 되었는지bool selected[MAX_N];// 각 팀의 능력치 계산 후 차이의 최솟값을 갱신하는 함수void upda.. [Algorithm] Segment Tree 문제Prefix Sum 배열을 이용하면 누적합을 O(n) 시간에 구할 수 있다.=> O(logn)에 누적합을 구할 수 있는 방법은 없을까?=> 배열을 수정할 수 있는 방법은 없을까? Segment Tree - 완전 이진 트리이다. (배열로 표현할 수 있다.)- 리프노드는 배열의 각 원소 값을 갖는다.- 각 노드는 왼쪽 자식 노드와 오른쪽 자식 노드 값의 합을 갖는다.- 노드의 개수는 배열의 요소 개수의 4배가 된다.합 구하기각 노드가 나타내는 구간이 [start, end]일 때, [left, right] 합을 구하는 방법은? 루트부터 차례대로 다음을 점검한다. (4가지 경우의가 존재한다.) 1. [start, end]와 [left, right]가 겹치지 않는다.=> 아무것도 하지 않는다. 2. [star.. [백준/C++] 4072번: Words 문제https://www.acmicpc.net/problem/4072문제 요약문장을 한 줄씩 입력 받고, 공백을 기준으로 각 단어를 뒤집어서 문장을 출력한다. "#"을 입력 받으면 종료한다.코드#include #include #include #include using namespace std;int main() { while (true) { string str; // 공백 포함 입력 받기 getline(cin, str); if (str == "#") break; // String을 StringStream 형으로 변환한 strs 선언 stringstream strs(str); string tmp; // strs 에서 " " 단위로 하나씩 추출하여 tmp에 저장 while (strs >> .. [백준/C++] 11727번: 2×n 타일링 2 문제https://www.acmicpc.net/problem/11727문제 요약2 × n 직사각형을 1 × 2, 2 × 1, 2 × 2 타일로 채우는 방법의 수를 출력한다. 코드#include #define MAX_N 1000using namespace std;int n;int dp[MAX_N + 1]; // dp[i]: 크기 i까지 타일로 채우는 방법의 수int main() { cin >> n; dp[1] = 1; dp[2] = 3; for (int i = 3; i 코드 설명Bottom - Up 방식의 다이나믹 프로그래밍을 통해 문제를 해결한다. 메모이제이션 테이블 dp를 정의한다. dp[i] = 2 × i 직사각형을 1 × 2, 2 × 1, 2 × 2 타일로 채우는 방법의 수 = 2 × (i .. 이전 1 ··· 9 10 11 12 13 14 15 ··· 52 다음
