꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/11976 어렵게 생각할 것 없이 silver의 차, gold의 차, platinum의 차만 알면 풀 수 있는 문제였습니다. #include #include using namespace std; int diff[4]; int main(void) { for (int i = 0;i > a >> b; diff[i] = b - a; } cout

문제 링크입니다: https://www.acmicpc.net/problem/2799 간단한 배열 문제였습니다.vector와 string을 연습하기 좋은 문제인 것 같아서 풀어봤습니다. #include #include #include using namespace std; int arr[5]; vector v; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int M, N; cin >> M >> N; v.resize(5 * M + 1); //총 5M + 1 줄 for (int i = 0; i > v[i]; for (int i = 0; i < 5 * M + 1; i++) { //#으로만 이루어진 줄인지 창문 윗..

문제 링크입니다: https://www.acmicpc.net/problem/1199 오일러 서킷(회로)은 그래프의 모든 간선을 정확히 한 번씩 지나면서 시작점과 끝점이 같습니다.오일러 회로에 대한 개념은 종만북에도 잘 쓰여있고 kks227님의 블로그(https://kks227.blog.me/220800097205)에도 정말 잘 설명되어있습니다.오일러 회로는 DFS(Depth First Search) 알고리즘을 통해 구현할 수 있습니다. 알고리즘은 아래와 같습니다.1. 오일러 회로의 경우 모든 정점의 간선 차수가 짝수여야 합니다.-> 두 개가 홀수여도 되는 경우는 오일러 회로가 아닌 오일러 경로 즉, 오일러 트레일입니다!2. 오일러 회로가 될 수 있는 조건을 성립한다면 1번 정점부터 해당 정점과 연결되어 ..

문제 링크입니다: https://www.acmicpc.net/problem/9666 이분 그래프(Bipartite graph)와 이분탐색을 이용하여 푸는 문제였습니다.문제에서 요구하는 바는 제일 효율적으로 팀을 나누었을 때 첫 번째로 같은 팀 출신의 선수가 마주치는 싸움의 순서를 구하는 것입니다. 알고리즘은 아래와 같습니다.1. 선수들이 입력될 때 양방향 그래프로 입력을 받고 몇 번째 싸움인지도 저장합니다.2. 이분 탐색을 진행해서 해당 싸움이 같은 팀끼리 싸우는지 혹은 다른 팀끼리 싸우는지를 확인합니다.-> 몇 번째 싸움인지 저장하는 이유가 여기서 나옵니다. 이분 탐색을 할 때 해당 싸움 이후로는 확인할 필요가 없습니다.3. 이분 탐색이 끝나고 나면 low에 제일 처음으로 같은 팀끼리 싸운 경기의 순서..

문제 링크입니다: https://www.acmicpc.net/problem/10881 박스의 회전까지 고려해야했기 때문에 접근하기 까다로웠던 문제였습니다.다행히 박스가 3개로 고정이였기 때문에 구현 자체는 크게 어렵지 않았습니다. 알고리즘은 아래와 같습니다.1. 박스의 배치는 크게 두 가지로 나뉠 수 있습니다.i) 일렬ii) 두개 밑에 위에 하나2. 가로와 세로를 입력 받을 때 90도 회전했을 때의 길이도 저장합니다.3. 1번에서 말했던 두 가지 경우의 수로 나누어 모든 가능한 크기를 구하고 그 중 최소를 출력해줍니다. #include #include using namespace std; const int INF = 987654321; int width[6], height[6]; int minBoxAre..

문제 링크입니다: https://www.acmicpc.net/problem/11876 수학적으로 접근해야하는 문제였습니다. 알고리즘은 아래와 같습니다.1. 핵심은 주어진 키 값들을 오름차순으로 정렬하고 해당 키가 몇 번 눌리는지를 구하는 것이였습니다.2. v[i]보다 작은 키들이 i - 1개이므로 v[i]가 눌리는 횟수는 i - 1개의 키들 중 k - 1개를 선택하는 조합입니다. -> (i - 1Ck - 1)3. 따라서, k - 1Ck - 1 ~ n - 1Ck - 1의 합을 더해주면 답이 됩니다. N의 최대값이 100,000이고 K의 최대값은 50이기 때문에 DP로 조합을 구해도 상관이 없지만,시간복잡도를 낮추기 위해 연두님이 팀노트에 작성하셨듯이 역원을 이용해 O(N) 안에 조합을 구할 수 있습니다.(..

문제 링크입니다: https://www.acmicpc.net/problem/11875 문제에서 요구하는 바는 문자열을 문자열의 부분 문자열의 조합으로 만들 수 있을 때, 길이가 제일 작은 부분 문자열을 구하는 문제였습니다.예를 들어, bbabab가 주어졌을 때, 부분 문자열 bba를 적절히 순서를 바꾸면 bab가 되므로 요구하는 답은 bba입니다. 알고리즘은 아래와 같습니다.1. 문자열이 부분 문자열의 조합으로 이루어져있어야하기 때문에 부분 문자열의 길이가 문자열의 길이로 나누어 떨어져야합니다.2. 해당 부분 문자열로 다른 부분 문자열을 만들 수 있는지 없는지를 판별하기 위해 알파벳 오름차순 정렬을 하여 같으면 가능하고 다르면 불가능하다고 판별합니다.3. 최초로 조건을 만족하는 부분 문자열을 출력하고, ..

문제 링크입니다: https://www.acmicpc.net/problem/11874 매우 간단한 문제였습니다. 제일 작은 수는 L ~ D까지 순회하면서 최초로 조건을 만족하는 숫자, 제일 큰 수는 D ~ L까지 순회하면서 최초로 조건을 만족하는 숫자입니다. #include using namespace std; int getSum(int num) { int sum = 0; while (num) { sum += num % 10; num /= 10; } return sum; } int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int L, D, X; cin >> L >> D >> X; for (int i = L; i

문제 링크입니다: https://www.acmicpc.net/problem/2661 string의 substr 함수를 잘 이용해야하는 백트래킹 문제였습니다. 알고리즘은 아래와 같습니다.1. 1, 2, 3으로만 이루어지므로 반복문을 통해 1, 2, 3을 더해나갑니다.2. 조건이 최초로 만족할 경우가 제일 작은 숫자이므로 출력하고 exit(0)를 통해 프로그램을 종료합니다.3. substr을 이용하여 인접한 부분 문자열이 같은지 확인합니다. #include #include using namespace std; int N; string num; void permutation(char c, int cnt) { //조건 만족(제일 먼저 나오는 숫자가 제일 작은 수) if (cnt - 1 == N) { cout

문제 링크입니다: https://www.acmicpc.net/problem/1443 얼핏 봐서는 매우 쉬운 문제이지만 방문 처리가 까다로울 수 있는 문제입니다. 알고리즘은 간단합니다.1. 1부터 시작해서 2 ~ 9를 P번 곱합니다. 즉, 결과는 8^P개가 나올 수 있다는 뜻!2. 따라서, 적절히 가지치기를 해줘야합니다.i) 자릿수가 D를 넘어가는 경우ii) cnt번 연산했을 때 똑같은 값이 나온 경우가 있는 경우3. 하지만, boolean 배열을 [1,000,000,000][30]는 크기가 너무 크기 때문에 선언할 수 없습니다.-> 따라서, map을 이용하여 저장합니다.4. 초기에 maxNum을 -1로 초기화하고 maxNumber 함수를 호출한 뒤 maxNum을 출력해주면 됩니다. #include #in..