꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1152 공백이 포함된 문자열이기 때문에 getline을 통해 입력받는 것이 핵심인 문제였습니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); string s; getline(cin, s); bool space = true; int cnt = 0; for (int i = 0; i < s.length(); i++) { if (s[i] == ' ') space = true; else if (space) { space = false; cnt++; } } cout

문제 링크입니다: https://www.acmicpc.net/problem/1726 매우 흥미로운 BFS(Breadth First Search) 문제였습니다. 알고리즘은 아래와 같습니다.1. 그래프를 입력받고 시작점과 도착점을 입력받습니다.2. 평범한 BFS처럼 시작하지만 처음에는 해당 방향으로 1, 2, 3칸을 갈 수 있는지 반복문을 통해 확인합니다.i) 해당 방향으로 좌표를 이미 방문했다면 다음 칸을 확인합니다.ii) 해당 방향으로 가는 좌표가 막혀있을 경우 이후 칸도 못 가기 때문에 반복문을 탈출합니다.iii) 해당 방향으로 갈 수 있는 좌표들은 큐에 넣습니다.iv) 갈 수 있는 1, 2, 3칸 모두 횟수가 1번만 증가합니다.3. 이후에는 방향전환을 할 수 있는지 확인합니다.i) 180도 방향전환하..

문제 링크입니다: https://www.acmicpc.net/problem/2004 숫자의 끝자리 0의 개수는 소인수 분해했을 때 min(2의 개수, 5의 개수)입니다.우선, 조합의 공식을 살펴봅니다.nCm = n! / (m!(n-m)!)이기 때문에 우리가 원하는 결과는 min(n!의 2의 개수 - m!의 2의 개수 - (n-m)!의 2의 개수, n!의 5의 개수 - m!의 5의 개수 - (n-m)!의 5의 개수)입니다.하지만 주어진 숫자는 최대 2,000,000,000이기 때문에 브루트 포스로 2의 개수와 5의 개수를 구한다면 TLE가 발생합니다.2와 5의 개수를 빠르게 구하기 위해서는 반복문을 조금 변형시켜야하는데 알고리즘은 아래와 같습니다. 알고리즘을 일반화시키기 위해 구하는 숫자를 i라고 하겠습니..

문제 링크입니다: https://www.acmicpc.net/problem/1629 시험 공부가 지긋지긋해서 푼 문제입니다.브루트 포스로 접근하면 B의 최대값이 2억이 넘기 때문에 TLE가 발생합니다.따라서, 분할 제곱을 이용하여 풀어야했던 문제였습니다. #include using namespace std; long long pow(int A, int B, int C) { if (B == 1) return A; else { long long temp = pow(A, B / 2, C); //B가 홀수면 A를 한번 더 곱해줘야한다 if (B % 2) return ((temp*temp) % C * A) % C; else return (temp*temp) % C; } } int main(void) { ios_b..

문제 링크입니다: https://www.acmicpc.net/problem/1181 생각보다 예외처리해야할 부분이 많은 문제였습니다.같은 단어를 입력받지 않기 위해 map을 사용하였고 정렬을 위해 cmp 함수를 직접 정의했습니다. #include #include #include #include #include using namespace std; bool cmp(string a, string b) { if (a.length() < b.length()) return true; //같은 길이인 경우 사전 순서 if (a.length() == b.length()) { for (int i = 0; i < a.length(); i++) if (a[i] == b[i]) continue; else if (a[i] <..

문제 링크입니다: https://www.acmicpc.net/problem/1427 algorithm 헤더의 sort를 연습하기 좋은 문제였습니다. #include #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N; cin >> N; vector num; while (N) { num.push_back(N % 10); N /= 10; } sort(num.begin(), num.end(), greater()); for (int i = 0; i < num.size(); i++) cout

문제 링크입니다: https://www.acmicpc.net/problem/12110 그리디하게 접근하면 O(N)으로 풀 수 있는 문제였습니다. 알고리즘은 아래와 같습니다.1. 시작점으로부터 출발을 합니다.2. 거리 D 내에 전화가 있으면 해당 전화기로부터 다시 출발합니다.3. 최대거리(D)를 갔는데도 전화가 없다면 해당 지점에 전화를 설치하고 다시 출발합니다. #include using namespace std; const int MAX = 300000 + 1; int N, D; bool phone[MAX]; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> D; for (int i = 0; i > ..

문제 링크입니다: https://www.acmicpc.net/problem/10611 처음에는 덱을 이용하여 직접 시뮬레이션을 하였더니 시간 복잡도가 O(N^2)이 나와 TLE가 발생했던 문제였습니다.문제의 입력은 최대 100,000개이기 때문에 O(N)으로 풀어야 AC를 받을 수 있는 문제였습니다. 알고리즘은 아래와 같습니다.1. {밀의 높이, 해당 높이 등장한 횟수}를 저장하는 덱을 선언하고 밀의 높이 오름차순으로 저장합니다.2. 애초에 밀의 높이 종류가 3 미만이면 Slavko가 이깁니다. 따라서, Slavko가 이긴다고 가정합니다.3. 직접 시뮬레이션을 하지 않으려면 최소높이 밀의 개수와 최대높이 밀의 개수를 파악해야합니다.i) 최소높이 밀의 개수가 최대 높이 밀의 개수보다 작거나 같다면 Mirk..

문제 링크입니다: https://www.acmicpc.net/problem/7572 "2013년이 "F9"로 표현된다는 사실을 이용하시오." 이 문장이 핵심인 문제였습니다.간지는 4년이 최초 년도이기 때문에 이를 고려해야합니다! #include #include using namespace std; string gab = "ABCDEFGHIJKL"; string gan = "0123456789"; int main(void) { int N; cin >> N; if (N == 1) { cout

문제 링크입니다: https://www.acmicpc.net/problem/10250 간단한 수식 문제였습니다. #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int T; cin >> T; for (int t = 0; t > H >> W >> N; N--; int Y = N % H + 1; int X = N / H + 1; cout