C++

https://www.acmicpc.net/problem/1987 1987번: 알파벳문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한www.acmicpc.netDFS와 되추적 기법(1,1)에서 시작되는 노드를 따라 갔던 정점 빼고 가장 많은 정점의 수를 출력해야한다. 즉, (1,1)에서 시작하여 모든 노드를 방문하며 - > DFS / BFS모든 경우의 수를 생각해야한다 -> 되추적 기법 모든 경우의 수를 생각해야하는 거면 DP도 되지 않나라는 생각을 했는데2차원 배열이 사용되는 그런 길? 타일 같은 공간이 필요하면 되추적으로 하는 것 같다(..) 되추..

🔗 문제 16235번: 나무 재테크 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 제한 1 ≤ N ≤ 10 1 ≤ M ≤ N^2 1 ≤ K ≤ 1,000 1 ≤ A[r][c] ≤ 100 1 ≤ 입력으로 주어지는 나무의 나이 ≤ 10 입력으로 주어지는 나무의 위치는 모두 서로 다름 🖍 풀이 처음에는 나무를 list에 저장하고 폐사할 경우 -1로 표기하고 해마다 정렬했는데 시간초과였다. 나이 오름차순으로 양분을 먹이려고 정렬을 이용했고, 새로 생기는 나무를 push_front()로 넣어도 시간초과..

🔗 문제 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com [S/W 문제해결 응용] 5일차 - 단순도금비용 🖍 풀이 🚩 주의: 단순도금비용은 Pass지만, 도금 비용은 Fail이에요. 문제를 보면 가장 큰 필름부터 붙이는 것이 좋겠다는 생각이 든다. 1) 먼저 손상 개수별로 최소 비용으로 수리할 수 있는 필름 크기를 알아보자. 9~5개는 사이즈가 3인 필름을 붙이는 것이 최소 비용 4~2개는 사이즈가 2인 필름을 붙이는 것이 최소 비용 1개는 사이즈가가 1인 필름을 붙이는 것이 최소 비용 이를 토대로 손상 개수 범위를 지정했다. const int size_range[3][2] = ..

🔗 문제 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 🖍 풀이 DFS는 시간초과고 BFS이라고 생각해서 풀면 오답이다. (경험담) 왜냐하면 생각해보면 map의 좌표 (x, y)까지 오는 경로는 다양하다. 가는 길이 0, 1로만 이루어진 것이 아니기 때문에 첫 방문이 최소 경로라고 단정지을 수 없다. 그래서 상하좌우로 이동하면서 (x, y)까지 걸린 시간을 계속해서 갱신해주어야 한다. visited[x][y]로 재방문를 판단하기는 하지만 그냥 갱신인지 신규인지만 판단하는 용도로 사용해줬다. 다익스트라의 개념을 알고 있으면 내 풀이를 이해하는데 도움됨 💾 소스 #include #..

문제 https://www.acmicpc.net/problem/2164 풀이 🚩원형 큐 앞에 카드를 빼고 뒤로 넣는다? -> 선입선출 -> queue 문제구나. 라이브러리를 사용하면 쉽게 풀 수 있고, 클래스로 직접 구현해서 풀어도 된다. 나는 겸사겸사 queue 라이브러리를 꼼꼼히 볼겸 간단하게 직접 구현해서 풀었다. Queue 라이브러리의 내부 코드가 궁금하면 아래 사이트를 참조하면 된다. https://en.cppreference.com/w/cpp/container/queue 🚩군수열 서치 하다가 군수열로 규칙찾는 방법도 있더라.. 근데 난 못 알아들음 (〃⌒▽⌒〃)ゝ https://hoho325.tistory.com/138 소스 #include #define MAX_SIZE 500001 class..

🔗 문제 13458번: 시험 감독 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 🖍 풀이 총감독은 필수이기 때문에 최소 N명의 감독님. 그리고 우리가 구할 것은 부감독님의 인원이다. 부감독이 필요한 경우는 총감독이 감독하지 못한 사람이 있는 경우 - Ai - B > 0 필요한 부감독님 인원은 (Ai - B)%C == 0 일 때, (Ai-B)/C (Ai-B)%C != 0 일 때, (Ai-B)/C + 1 풀이가 필요할까..? 조건의 수가 크기 때문에 결과를..