본문 바로가기

알고리즘

 (82)
[백준] 23247번 Ten C++ 문제풀이 https://www.acmicpc.net/problem/23247 23247번: Ten A real estate company IC is managing a rectangular section of land. The section is divided into $mn$ segments in $m \times n$ matrix shape, where the number of rows and that of columns are $m$ and $n$, respectively. Each segment has its own price as a posi www.acmicpc.net 문제 풀이 맨 처음에 문제를 보자마자 누적합 배열을 만들어야하나 라고 생각했는데, 어떤식으로 풀어야 할지 모르겠어서 완전 탐색 방식으로..
[백준] 25953번 템포럴 그래프 C++ 문제풀이 https://www.acmicpc.net/problem/25953 25953번: 템포럴 그래프 템포럴 그래프는 시간의 흐름에 따라 변화하는 관계를 표현하는 자료 구조이다. 템포럴 그래프를 구성하는 정점 집합 $V$는 시간의 흐름에 따라 변하지 않으며, 정점의 개수가 $n ≥ 1$이라 할 때 www.acmicpc.net 문제 풀이 맨 처음에 그래프 탐색 문제인 줄 알고 DFS라고 함수명을 정한 뒤 문제를 풀었는데, 적는 지금 생각해보니 그냥 DP문제였다. 1차원 배열로 DP를 해결하려 했으나 39%에서 계속 틀리길래 왜 그런지 생각해보았는데, 알고보니 1차원 배열로 갱신하게 되면 중간에 값이 바뀌기 때문에 틀리게 되어버린다. void dfs(int s_time) { if (s_time == t) { re..
[백준] 25945번 컨테이너 재배치 C++ 문제풀이 https://www.acmicpc.net/problem/25945 25945번: 컨테이너 재배치 항구의 컨테이너 하치장 바닥에는 컨테이너를 쌓을 수 있는 칸이 일렬로 총 $n$개가 그려져 있고, 현재 하치장에는 총 $m$개의 컨테이너가 쌓여 있다. 개별 컨테이너의 높이는 모두 $1$로 동일하며 www.acmicpc.net 문제 풀이 컨테이너의 높이 차이가 1까지 허용되기 때문에 평균 값을 중심으로 컨테이너를 재배치 해야겠다고 생각했다. 값들을 저장한 뒤 내림차순으로 정렬하고 정렬한 숫자에서 합을 n으로 나눈 뒤 나머지 만큼의 컨테이너는 1개가 더 쌓여있을 것이기 때문에 컨테이너를 빼냈다. 평균 컨테이너수보다 적거나 같은 컨테이너들은 앞쪽에서 빼낸 컨테이너들을.채워 넣는 것이기 때문에 break를 시켜줬..
[백준] 25943번 양팔저울 C++ 문제풀이 https://www.acmicpc.net/problem/25943 25943번: 양팔저울 입력은 표준입력을 사용한다. 첫 번째 줄에 자갈 개수를 나타내는 양의 정수 $n$ ($2 ≤ n ≤ 10\,000$)이 주어진다. 다음 줄에 $n$ 개의 수들이 주어지는데, 이들은 번호 순서대로 자갈의 무게이다. 자 www.acmicpc.net 문제 풀이 규칙에 맞게 왼쪽 저울과 오른쪽 저울에 자갈을 놓은 다음, 차이 값만큼을 100g 부터 무게 추를 추가했다. 최종적으로 추가적으로 필요한 무게추의 최소 개수를 출력한다. 소스 코드 #include using namespace std; int chu[8] = { 100,50, 20, 10, 5, 2, 1 }; int input[10001] = { 0 }; int m..
[백준] 26111번 Parentheses Tree C++ 문제풀이 https://www.acmicpc.net/problem/26111 26111번: Parentheses Tree A rooted ordered tree $T$ can be expressed as a string of matched parentheses $p(T)$. The string representation $p(T)$ can be defined recursively. As a base case, a tree consisting of a single node is expressed by a pair of parentheses (). When a rooted or www.acmicpc.net 문제 풀이 처음에는 재귀를 이용해서 문제를 풀었는데, 입력 크기가 최대 10^7이기 때문에 당연히 시간초과가 떠..
[백준] 15486번 퇴사 2 C++ 문제풀이 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 풀이 DP를 통해서 문제를 해결하려고 했다. dp[i]에는 i-1날까지 끝낼 수 있는 상담을 통한 최대수익을 저장했다. 첫번째로 현재 dp값이 이전 dp값의 최대보다 작은 경우 갱신해주고, 두번째로 그 날 맡은 상담을 할 수 있는지, 아니면 N보다 커서 상담이 불가능한지를 고려하여 코드를 작성했다. 남들이 작성한 코드가 시간이 적게 걸린 것 봐서는 다르게 짜는 ..
[백준] 2293번 동전 1 C++ 문제풀이 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 DP문제라는걸 고려하고 문제 해결 방법을 고민하니 답이 금방 나왔다. 새롭게 경우의 수가 추가되는 경우를 생각해보니, dp[n] + dp[n - 현재 사용한 동전의 종류 크기] 를 하면 새로운 dp[n] 값이 나온다. 우리가 궁금한 값은 dp[k] 이므로 dp[k]까지 배열을 돌려주면 된다. 소스 코드 #include #include #include using namespace std; ..
[백준] 11053번 가장 긴 증가하는 부분 수열 C++ 문제풀이 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이 DP 문제의 특성을 이용해 한 번의 반복문으로 풀려고 했는데 잘 풀리지 않았다. 이중 반복문을 이용해 최장 증가하는 부분 수열 값을 구했다. 소스 코드 #include using namespace std; int num[1001] = { 0 }; int cnt[1001] = { 0 }; int main() {..

티스토리툴바