🔗 문제 링크 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 💡 문제 풀이 및 해석 처음에는 평균을 잡아놓고, 평균 아래의 가격과의 차액을 더하는 방식으로 할려 했지만, 차액을 더하는 도중에 평균보다 위였던 금액이 평균보다 낮아져 버릴 수도 있음을 알았다. 그래서 차라리 이분탐색으로 금액을 정해놓고 이 금액이 가능한지 판별하는 방식으로 접근하기로 했다. 만약 전체 금액 N; country = vector(N); for (int i = 0; i > country[i]; su..
알고리즘 문제 풀이
🔗 문제 링크 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 💡 문제 풀이 및 해석 일단, 보자마자 비싼 강의를 최대한 많이 들어야 한다는 것을 알 수 있다. 여기서 어떻게 들어야 할 것인가가 중요하다. 여기서 day로 정렬해서 한다면, 문제가 발생한다. 예를 들어서, 같은날 비싼 2개의 강의가 있을 때, 전날 강의를 버리고 그 다음날까지 유예기간이 있는 강의를 들을 수가 없기 때문이다. 여기서 해결방법으로는 아래와 같다. 가장 비싼 강의로 내림차순으로 정렬한다. 유예기간..
🔗 문제 링크 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 💡 문제 풀이 및 해석 N > N; dp = new int[N + 1]; building.push_back({ -1,-1 }); for (int i = 1; i > left >> right; building.push_back({ left,right }); dp[i] = 1; } sort(building.begin(), building.end()); } void sol() { int answer = 0; for (int i = 1; i building[j]..
🔗 문제 링크 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 💡 문제 풀이 및 해석 블루레이의 사이즈는 최대 10억이다. 따라서 최대 크기를 10억으로 잡아두고 시작한다. 블루레이의 사이즈를 이분탐색으로 정한다. 블루레이에 담기는 순서는 강의의 순서와 같으므로, 순서대로 블루레이에 강의를 담는다. 그렇게 블루레이가 꽉 차면 다음 블루레이에 담기는 순서로 이분탐색을 진행하면 된다. ⭐️ 정답 코드 및 설명 #include #include using namespace std; int N, M; vector lectur..
🔗 문제 링크 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 💡 문제 풀이 및 해석 치킨집은 13개 이하, 그냥 집은 최대 2N 이다. 조합으로 13개를 뽑는다면, 최대 13C6 이다. 따라서 1716 * 2 * 50 이므로 브루트포스하게 풀 수 있다. 이제 치킨집을 고른 뒤, 집마다 치킨집까지의 거리를 구하고 가장 가까운 거리를 계속 더해주면 된다. ⭐️ 정답 코드 및 설명 #include #include #define INF 987654321 using namespace std; in..
🔗 문제 링크 https://www.acmicpc.net/problem/9251 💡 문제 풀이 및 해석 '최장 부분 공통 수열' 문제는 DP를 사용한다. 어떻게 풀지 모르겠어서 구글링을 하여 아래 사이트에서 이해를 한뒤 풀었다. 주석을 풀면 myMap이 만들어진 것을 볼 수 있다. 도움을 받은 사이트 ⭐️ 정답 코드 및 설명 #include #include using namespace std; string str1, str2; //string answer = ""; int myMap[1001][1001]; void input() { cin >> str1 >> str2; } int sol() { for (int y = 1; y
🔗 문제 링크 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 💡 문제 풀이 및 해석 만약 카드의 숫자가 N개라면 반드시 N-1번의 계산을 해야 한다. 여기서 가장 적은 수를 더해야 한다. 항상 가장 작은 두 집합을 더해준다. 이러면 결과적으로 가장 작은 수가 나온다. 만약, 큰 수가 들어가게 된다면, 그 수는 총 연산에서 이번 연산을 제외하고 반드시 한번 더 들어가야 하므로 최소값이 될 수 없다. ⭐️ 정답 코드 및 설명 #include #include using namespace std; i..
🔗 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 문제 풀이 및 해석 매 skill마다 board를 바꾸면, 시간복잡도가 너무 증가한다. 따라서 매번 바꾸는 방식은 안된다. 여기서 누적합 혹은 DP방식으로 풀어야 한다는 것을 알 수 있다. 여기서 2차원 배열에서의 누적합으로 풀어야 하는데, 풀이 방식은 각 모서리에 마킹을 해두는 것이다. Attack 기준으로 아래 코드에서도 볼 수 있듯이 4x4 사이즈에서는 5x5 사이즈의 임시 맵의 모서리에 마킹을 해둔다. MAP[r1][c1] -= degree; MAP[r1][c2 + 1] += degr..
