GOLD23 [백준/C++] #15686 치킨 배달 (Brute Force) 문제https://www.acmicpc.net/problem/15686 구상처음에는 어떤 치킨집을 폐업시켜야 할까? 라는 고민을 통해 아래 처럼 풀이를 구상했었다. 1. bfs로 각각의 집들에서 가장 가까운 치킨집 방문, 치킨거리 갱신 2. 가장 방문이 많은 치킨집 순으로 최대 m개를 고르고 3. 나머지 치킨집이랑 가까웠던 집들은 다시 거리 계산해야 한다. -> 하지만, 방문이 많은 m개 집 고른다 해도 해당 집들이 최소 도시 치킨 거리를 만든다고 장담할 수 없다. 수정 후 풀이는 다음과 같았다. Brute force! 1. 치킨집 조합 만들기 -> next_permutation 이용!! 2. 각각의 치킨집에 대해 집들의 거리 구하기 3. 거리를 다 합친 도시 치킨 거리들 중 최소값 구하고 출력 next.. 2024. 7. 6. [백준/C++] #9251 LCS (DP/LCS) 문제https://www.acmicpc.net/problem/9251 구상사실.. 문제 이름 자체가 LCS여서... 바로 LCS 대입해서 풀었다. 알고리즘: LCS (Longest Common Subsequence) 두 수열이나 문자열에서 공통되는 가장 긴 부분수열 혹인 부분 문자열 중요한건, 공통되는 문자열이 연속적일 필요는 없다! LCS는 2차원 DP 배열을 통해 구할 수 있다. 풀이 + 코드if (현재 비교하는 문자가 서로 다르다면) 왼쪽, 위쪽 두 개의 값 중 큰 값 저장else 왼쪽 위 대각선의 값 + 1 저장 #include #include using namespace std;string s1, s2;vector> dp;/*9251 LCS*/int main() { cin >> s1 >> .. 2024. 7. 5. [백준/C++] #2473 세 용액 (Two Pointer) 문제https://www.acmicpc.net/problem/2473 구상세 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어야 하고, 이때의 세 용액을 출력해야 하는 문제였다. 두 용액 일 때는 아래와 같이 두개의 포인터를 이용해서 풀었었다. https://persi0815.tistory.com/entry/%EB%B0%B1%EC%A4%80C-2467-%EC%9A%A9%EC%95%A1-Two-Pointer 세 용액이면 어떡할까? 고민을 해봤는데, 한 용액을 고정한 뒤 나머지 두 용액을 투 포인터로 찾는 방법이 떠올랐다. 알고리즘: two pointer 풀이 + 코드용액 특성값들을 배열에 넣고 투포인터 사용을 위해 정렬을 했다. 그리고, 한 용액을 선택한 뒤, 나머지 두 용액을 결정하자. brut.. 2024. 7. 3. [백준/C++] #2467 용액 (Two Pointer) 문제https://www.acmicpc.net/problem/2467 알고리즘: two pointer 풀이 + 코드가장 기초적인 투포인터 문제다.(정렬된) 용액 특성들을 배열에 넣고, 두개의 포인터를 이용하여 배열 값들의 합을 구하며 0과 가장 가까운 값이 나타나면 답을 갱신한다. #include #include #include #include #define MAX 100001#define INF 987654321#define endl "\n"using namespace std;/*2467번 용액산성 용액: 1부터 1,000,000,000, 알칼리성 용액: -1부터 -1,000,000,000같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합같은 양의 두 용액을 혼합하여.. 2024. 7. 3. 이전 1 2 3 4 5 6 다음
