SM's Development Log

복기해당 문제가 그리디로 풀었을 때 정당성을 가지는 이유는 가지고 있는 거스름돈의 큰 단위가 항상 작은 단위의 배수기 때문이다. 코드C++ 17 #include int M;int Rests[] = { 500, 100, 50, 10, 5, 1 }; int main(){ scanf("%d", &M); int target = 1000 - M; int ans = 0; for (int i = 0; i < 6; ++i) { ans += target / Rests[i]; target %= Rests[i]; } printf("%d\n", ans);} C# 6.0 using System; namespace Csharp{ class Program { static readonly int TARO_MONEY = 1000; s..

복기괄호 쌍 찾는 문제와 비슷하다. 코드C++ 17 #include #include using namespace std; string Word, Bomb; // 끝에서부터 비교해 나가면 중첩되었더라도 삭제할 수 있다.bool CanExplode(const string& str){ if (str.back() != Bomb.back() || str.size() < Bomb.size()) return false; for (int i = 0; i < Bomb.size(); ++i) { if (str[str.size() - 1 - i] != Bomb[Bomb.size() - 1 - i]) return false; } return true;} int main(){ ios::sync_with_stdio(false);..

복기- 코드C++ 17 #include #include #include #include #include using namespace std; int N;set WordSet; bool Check(string& word){ // WordSet에 있는 모든 단어와 확인한다. for (const string& src : WordSet) { if (word.size() != src.size()) continue; for (int i = 0; i < word.size(); ++i) { if (src == word) return true; // 단어 크기만큼 단어를 돌려본다. rotate(word.begin(), word.begin() + 1, word.end()); } } return false;} int mai..

복기- 코드C++ 17 #include int N, R, C; int main(){ scanf("%d %d %d", &N, &R, &C); int ans = 0; while (N) { // 어느 사분면에 속해있는지 구분하기 위한 기준이다. int s = (1 = s) q = 1; // 3사분면 else if (R >= s && C = s && C >= s) q = 3; // 다음 계산을 위해 R, C의 값을 갱신한다. R %= s; C %= s; // 1사분면을 기준으로 값을 더한다. ans += (s * s) * q; --N; } printf("%d", ans);} C# 6.0 using System; namespace Csharp{ class ..

복기역을 통해 답을 구할 수 있는지 생각해보자. 코드C++ 17 #include using ll = long long; bool IsChecked[1000001];bool IsSquare[1000001]; int main(){ ll min, max; scanf("%lld %lld", &min, &max); // 제곱 ㄴㄴ수는 너무 많으므로 // 답의 개수 중 제곱수를 제외한다. ll ans = max - min + 1; for (ll i = 2; i * i

복기해당 문제는 ‘중국인의 나머지 정리’를 이용하면 더 빠르게 풀 수 있다. 코드C++ 17 #include int main(){ int E, S, M; scanf("%d %d %d", &E, &S, &M); // 구하고자 하는 수 x는 // x = 15a + 1 = 28b + 1 = 19c + 1이다. // 계산의 편의성을 위해 1을 빼준다. --E; --S; --M; // 정답을 구할 때까지 반복한다. int ans = E; while (!(ans % 28 == S && ans % 19 == M)) ans += 15; // 지금까지 구한 수는 x - 1이므로 ans에 1을 더해 출력한다. printf("%d", ans + 1);} C# 6.0 using System;using System.Collec..

복기문제를 해결하기 위해 어떤 순서로 답을 구해야 할지 고민하자. 코드C++ 17 #include #include #define INF 987654321#define MIN(a, b) ((a) 0) { K = Convert.ToInt32(Console.ReadLine()); var inputs = Console.ReadLine().Split(); for (int i = 1; i

복기메모이제이션을 하자 코드C++ 17 #include #define MAX(a, b) ((a) > (b) ? (a) : (b)) int N, Ans;int Arr[1001]; // Memo[i] : i번째를 수열의 마지막 수라고 할 때, 그 수열의 합// Memo[i] = Memo[j] + Arr[i] if Arr[j] < Arr[i]int Memo[1001]; int main(){ scanf("%d", &N); for (int i = 0; i < N; ++i) { scanf("%d", &Arr[i]); Memo[i] = Arr[i]; for (int j = 0; j < i; ++j) { if (Arr[j] < Arr[i] && Memo[i] < Memo[j] + Arr[i]) Memo[i] = Mem..

복기- 코드C++ 17 #include int Tree[10001];int N; void preToPost(int node, int bound){ // 오른쪽 서브트리의 시작 인덱스를 찾는다. int sub = node + 1; while (sub

복기데이터를 때에 따라 확장하자. 코드C++ 17 #include #include #include using namespace std; struct Elem{ int H, W;}; int H, W, T; // 빌딩 밖도 탐색의 범위에 포함시켜// 프로그래밍의 편의성을 가져간다.// 다시 말해, 왼쪽 맵을 오른쪽처럼 생각한다.// **.* ......// *..* --> .**.*.// **** .*..*.// .****.// ...... char Map[102][102];bool Keys[26];bool IsVisited[102][102];int dh[] = { -1, 1, 0, 0 };int dw[] = { 0, 0, -1, 1 }; int bfs(){ int ans = 0; queue q; // 추후..