꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/14647 간단한 탐색 문제였습니다. 알고리즘은 아래와 같습니다.1. 각 숫자에 포함된 9의 개수를 파악하는 함수를 정의합니다.2. 빙고판을 입력 받을 때 숫자로 입력받지 않고 각 숫자의 9의 개수로 입력받습니다.-> 이 때, 9가 최대로 많이 있는 열도 파악합니다.-> 모든 9의 개수를 파악합니다.3. 9가 최대로 많이 있는 행을 파악합니다.4. 2번에서 구한 모든 9의 개수 - max(2번에서 구한 열, 3번에서 구한 행)이 정답입니다. #include #include using namespace std; const int MAX = 500; int N, M; int bingo[MAX][MAX]; //9의 개수 파악 int f..

문제 링크입니다: https://www.acmicpc.net/problem/14646 시간복잡도 O(N)으로 풀 수 있는 탐색 문제였습니다. 알고리즘은 아래와 같습니다.1. 기존에 선택되지 않았던 칸이라면 벡터에 넣고 선택되었다고 표시합니다.2. 기존에 선택되었던 칸이라면 지워야하는데 실제로 지우지 않고 지운 원소를 증가시킵니다.3. 반복문의 끝마다 현재 스티커가 붙여있는 개수를 파악하고 최대 개수를 초기화합니다. #include #include #include using namespace std; const int MAX = 100000 + 1; int N; vector wheel; bool selected[MAX]; int main(void) { ios_base::sync_with_stdio(0); ..

문제 링크입니다: https://www.acmicpc.net/problem/14659 브루트 포스(Brute Force) 알고리즘 문제였습니다. 알고리즘은 아래와 같습니다.1. [0~N)까지 반복문을 돌리면서 arr[i]를 기준 봉우리로 만듭니다.2. [i+1 ~ N)까지 반복문을 돌리면서 1번에서 기준으로 삼은 봉우리보다 작은 봉우리들의 개수를 기준 봉우리보다 큰 봉우리가 나올 때까지 셉니다.3. 2번에서 구한 값 중 최대를 출력합니다. #include #include using namespace std; const int MAX = 30000; int N;int arr[MAX]; int main(void){ ios_base::sync_with_stdio(0); cin.tie(0); //cin 실행속도..

문제 링크입니다: https://www.acmicpc.net/problem/14658 우선, N과 M이 최대 500,000이기 때문에 브루트 포스(Brute Force) 방식으로는 절대 풀 수 없는 문제입니다.하지만 K는 최대 100이기 때문에 입력한 좌표를 통해서 풀 수 있을 것이라고 유추할 수 있습니다. 알고리즘은 아래와 같습니다.1. [0 ~ K)까지 이중 반복문을 돌립니다.(i, j)2. i번째 좌표를 정사각형의 좌상단 좌표로 지정하고 j번째 좌표를 정사각형의 우상단 좌표로 지정합니다.3. 이제 [0~K)까지 반복문을 한번 더 돌리는데 2번에서 지정한 영역 내에 있는 좌표들의 개수를 구합니다.4. 3번에서 구한 값 중 최대 값을 구합니다.5. 4번에서 구한 값은 트램폴린에 들어가는 별똥별이기 때문..

문제 링크입니다: https://www.acmicpc.net/problem/14657 백준 1967번 트리의 지름(http://jaimemin.tistory.com/531)에서 한 단계 더 응용해야하는 문제였습니다.따라서, DFS 함수 매개변수에 length라는 매개변수를 추가해서 동일한 지름이 있다면 가중치의 합이 더 작은 쪽을 선택하도록 했습니다. 알고리즘은 아래와 같습니다.1. 우선, 루트에서 가장 멀리 떨어져 있는 노드를 찾습니다.i) 루트 기준으로 가중치의 합이 제일 낮은 지점을 찾습니다.2. 가장 멀리 떨어져 있는 노드 기준으로 가장 멀리 떨어져 있는 노드까지의 경로가 트리의 지름입니다.i) 현재 저장된 지름보다 length가 더 클 경우 지름을 length로 초기화하고 가중치를 cost로 초..

문제 링크입니다: https://www.acmicpc.net/problem/14656 1~N까지 학생들을 탐색하는데 해당 인덱스와 동일하지 않은 학생들의 수를 세면 되는 간단한 문제였습니다. #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); //cin 실행속도 향상 int N; cin >> N; int result = 0; for (int i = 1; i > num; if (num != i) result++; } cout

문제 링크입니다: https://www.acmicpc.net/problem/14655 문제의 아래 조건을 이해하는 것이 핵심인 문제였습니다."욱제는 연속한 3개의 동전을 뒤집지 않으면 이길 수 없다고 생각하기 때문에 실패하는 경우 없이 항상 연속한 3개의 동전만 뒤집는다. 동전 배열의 양 끝에서 벗어나서 양 끝의 동전만 뒤집거나 양 끝의 두 개 동전만 뒤집는 것도 가능하다. 동전을 뒤집는 횟수에 제한은 없다." 결국, 같은 동전을 1번 이상 뒤집을 수 있기 때문에 원하는대로 동전을 배치할 수 있습니다.따라서 아래와 같이 그리디(Greedy)하게 접근할 수 있습니다.1 라운드에서는 합이 최대가 되도록 모두 양수로 만들어줍니다.2 라운드에서는 합이 최소가 되도록 모두 음수로 만들어줍니다.따라서 (1 라운드 ..

문제 링크입니다: https://www.acmicpc.net/problem/14654 단순 구현 문제였습니다.문제에서 요구하는대로만 구현을 한다면 AC를 받을 수 있는 문제였기 때문에 설명은 생략하겠습니다. #include #include using namespace std; const int MAX = 300; int N; pair arr[MAX]; int maxStraightWins(void) { int team1 = 0, team2 = 0; int result = 0; for (int i = 0; i < N; i++) { //비긴 경우 새로 출전한 사람이 승을 챙김 if (arr[i].first == arr[i].second) { if (!team1) { team1++; result = max(re..

문제 링크입니다: https://www.acmicpc.net/problem/14653 기본적으로 Q번째 톡을 읽은 사람들은 1 ~ (Q - 1)번째 톡도 읽었다는 것이 핵심인 문제였습니다. 알고리즘은 아래와 같습니다.1. Q 번째 톡을 안 읽은 사람이 0명이면 전원 읽었으므로 -1을 출력합니다.2. 1번의 경우가 아니라면 Q 번째 톡을 안 읽은 사람과 같거나 적은 톡을 보낸 사람들은 Q번째 톡을 읽은 사람이기 때문에 Read에 표시를 합니다.3. Read에 표시되어 있지 않은 사람들을 출력합니다. *기존에 Read 함수를 read로 정의했다가 read 라는 이름을 가진 unix system call 함수랑 충돌해서 런타임 에러가 발생했었습니다. #include using namespace std; con..

문제 링크입니다: https://www.acmicpc.net/problem/14652 간단한 계산 문제였습니다.특별한 알고리즘을 요구하지 않는 문제이기 때문에 코드만 포스팅하겠습니다. #include using namespace std; int main(void){ ios_base::sync_with_stdio(0); cin.tie(0); int N, M, K; cin >> N >> M >> K; cout