너와 나의 스토리

문제: https://www.acmicpc.net/problem/2579 문제 풀이: 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. => K번째 계단을 밟을 수 있는 경우는 다음과 같다: 1. stairs[K-3], stairs[K-1] -> stairs[K] 2. stairs[K-2] -> stairs[K] 위 그림과 같이 항상 조건을 만족하게 된다. 소스 코드: 더보기 #include #include using namespace std; int n,arr[305],dp[305]; int main() { ios::sync..

A - https://codeforces.com/contest/1294/problem/A 소스 코드: 더보기 #include #include using namespace std; int tc; long long a, b, c, n; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> tc; while (tc--) { cin >> a >> b >> c >> n; long long max_num= max(a, max(b, c)); long long fsum = max_num * 3 - a - b - c; if (n - fsum n; v.clear(); string s=""; bool flag=tr..

문제: https://www.acmicpc.net/problem/1049 테스트 케이스: Input Output 8 1 30 4 32 소스 코드: 더보기 #include #include #define inf 987654321 using namespace std; int n,k; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> k; int package = inf, unit = inf; for (int i = 0; i > a >> b; package = min(package, a); unit = min(unit, b); } int res = 0; if (p..

문제: https://www.acmicpc.net/problem/1158 이중 연결 리스트(Doubly Linked List) 소스 코드: 더보기 #include using namespace std; int n, k; class linkedlist { public: class node { public: int num; node *right; node *left; node(int n) { num = n; left = NULL; right = NULL; } }; node *head; void insert() { head = new node(1); node *cur = head; for (int i = 2; i right= newone; newone->left = cur; cur = newone; } cur-..

문제: https://leetcode.com/problems/flip-string-to-monotone-increasing/ 문제 설명: 0과 1로 주어진 문자열이 주어진다. 0 다음 1이 나오는 순서로 만들기 위해 (0을 1로) (1을 0으로) 변환하는 최소 횟수를 리턴하라. 문제 풀이: 0의 개수를 축적해서 기록 -> zero[] 결국 000111 이런식으로 변환되는 것으로 명확한 boundary가 생기게 된다. 모든 위치를 boundary로 잡고, boundary 왼쪽은 0이 되도록, 오른쪽은 1이 되도록 할 때, 바꿔야할 개수를 찾는다. 결과를 저장할 변수(res)를 처음에는 '전부 1인 문자열이 되도록 할 때, flip 수'로 초기화한다. 모든 boundary에서 res=min(res, 왼쪽에 ..

문제: https://www.acmicpc.net/problem/5446 문제 풀이: 1. 지워야 할 파일들을 trie에 insert 2. 지우면 안 될 파일들이 이름이 trie에 존재하는 것들과 겹치는 부분을 체크 (no=true) 3. 전체 trie 순환하면서 no가 아닌 부분에 도달하면 res++하고 그 라인은 더 이상 보지 않음 * [rm *]이 가능하려면 root에 존재하는 모든 next에 대해 no 플래그가 off 되어 있어야 한다. 이를 체크하기 위해 2번 작업을 수행하다 no를 한 번이라도 체크하게 되면 root->no=true가 되게 하였다. root->no가 false라면 rm *이 가능하므로 답은 1이 된다. 소스코드: #include #define QSIZE 63002 using n..

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18OR16IuUCFAZN#none 문제 풀이: 1. 0이 아닌 직사각형들 찾기 2. 행렬들을 곱셈 가능한 순서로 나열 -> "1259. [S/W 문제해결 응용] 7일차 - 금속막대" 문제와 동일한 풀이법 -> 이 블로그의 풀이를 참고하였습니다. 3. 연쇄 행렬 최소 곰셈 알고리즘 사용 -> 2019/11/22 - [알고리즘/기타] - [BOJ] 11049 행렬 곱셈 순서 소스 코드: #include #include #include #define inf 987654321 using namespace std; typedef pair P; vector v; in..

문제: https://www.acmicpc.net/problem/11049 문제 풀이: 연쇄 행렬 최소 곱셈 공식 - DP 소스 코드: #include #include #include #define inf (1 n; for (int i = 0; i > a >> b; d[i] = a; if (i == n - 1) d[i + 1] = b; } for (int diagonal =0; diagonal < n; diagonal++) { for (int i = 1; i