정화 코딩

https://www.acmicpc.net/problem/2331 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int a, p; cin >> a >> p; vector ans; ans.push_back(a); int idx = -1; int cur = a; while (1) { int nxt = 0; while (cur > 0) { int rem = cur % 10; int tmp = 1; for (int i = 0; i 단순..

https://www.acmicpc.net/problem/1111 #include #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector arr(n); for (int i = 0; i > arr[i]; set ans; for (int a = -200; a 2) cout 무지성으로 모든 a, b 조합을 체크해서 풀었다...처음에는 a와 b 범위 모두 -100 ~ 100으로 잡았다가 WA를 받았다. 그 후 범위가 부족함을 깨닫고 범위를 늘려줬다. 무지성으로 너무 늘리면 또 시간초과를 ..

https://www.acmicpc.net/problem/25709 #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int ans = 0; string s = to_string(n); string tmps = ""; for (char c: s) { if (c == '1') ans++; else tmps += c; } if (tmps.empty()) n = 0; else n = stoi(tmps); while (n > 0) { int tmp = n..

https://www.acmicpc.net/problem/30805 구현할 때 신경쓸 게 좀 많아서 번거롭다고 느낀 문제였다. 우선 나는 다음과 같이 구현하였다.  일단 이 문제는 그리디로 풀 수 있다. 왜냐하면 구해야 하는 것이 "사전 순 최대" 공통 부분 수열이기 때문이다. 길이만 가장 길어야 하는 거면 dp로 풀어야 하지만, 사전 순으로 했을 때 가장 나중인 것을 선택하면 되므로 그리디하게 공통되는 최댓값을 쭉 선택하면 된다.  다시 정리하자면, 공통되는 수 중 최댓값을 찾고, 그 수의 오른쪽을 기준으로 또 다시 공통되는 수 중 최댓값을 찾고... 를 반복하면 된다.  구체적인 구현은 이렇다.  우선 a 배열에서 최댓값을 찾는다. 찾은 최댓값이 b 배열에도 있는지 확인한다.만약 없다면 아까 a 배열..

https://www.acmicpc.net/problem/27966 #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); long long n; cin >> n; long long ans = (n - 1) + (n - 1) * (n - 2); cout 모든 정점 쌍에 대해서 두 정점 사이 거리의 합이 최소가 되도록 하기 위해서는 하나의 정점을 중심에 두고 나머지 모든 정점을 그 중심 정점에 연결하도록 트리를 구성하면 된다. 이 사실만 알면 쉽게 풀 수 있었던 문제. 아 long long으로 해야 함! (AC)

https://www.acmicpc.net/problem/31460 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) { int n; cin >> n; if (n == 1) { cout 011121122112221122221...이렇게 규칙만 찾으면 쉽게 풀 수 있는 문제. 0도 11의 배수임에 주의하자. (AC)

https://www.acmicpc.net/problem/23817 이 문제 풀 때 고수들이 옆에 있었어서 그들이 걍 다 해줌. 저는 풀이를 듣고 음 그렇구나. 천재다. 구현해볼게. 했음다. 첫번째 풀이. vst 배열: 현재 위치 (i, j) + 어느어느식당 방문했는지 (길이가 20인 비트스트링) 길이가 20인 비트스트링 → 2^20 하면 너무 큼 → 근데 어차피 최대가 5개 켜지는 거임 → 2^20 중에 안 쓰는 게 너무 많음 (어떤 걸 안 쓰는지 모름) → map 이용 vector>> → 최단 거리를 두번째 int에 저장하는 셈 vector>> (= vector>>) → 방문 했는지 안 했는지를 bool에 저장하는 셈 근데 이렇게 하면 터짐...  두번째 풀이.모든 식당과 식당 (+시작점) 사이의 거..

https://www.acmicpc.net/problem/13172 이 문제의 핵심을 정리하면 아래와 같다. 기약분수 a/b를 다음과 같이 하나의 정수로 표현할 수 있다.  이 때 X는 1,000,000,007과 같은 큰 소수이다.b^(-1)은 b의 모듈러 곱셈에 대한 역원인데, 다음과 같이 계산할 수 있다.  이 정도만 알면 문제를 풀 수 있다. 이제 구체적으로 어떻게 구현할지 생각해보자.한 줄에 분모와 분자 순서대로 한 쌍의 분수가 들어온다. 각 분수에 대해 a * b^(-1) mod X 를 구하면 된다. 그리고 모든 값들을 마치 확률을 더하듯 그냥 더해주면 된다.  내가 헷갈렸던 점은 기약분수 a/b에 대해서 저렇게 계산해야 된다고 하길래 들어온 분모와 분자에 대해서 우선 기약분수 형태로 만들어줘야..