[백준] 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..

• format_list_bulleted 알고리즘
• · 2023. 9. 23.

[백준] 25945번 컨테이너 재배치 C++ 문제풀이

https://www.acmicpc.net/problem/25945 25945번: 컨테이너 재배치 항구의 컨테이너 하치장 바닥에는 컨테이너를 쌓을 수 있는 칸이 일렬로 총 $n$개가 그려져 있고, 현재 하치장에는 총 $m$개의 컨테이너가 쌓여 있다. 개별 컨테이너의 높이는 모두 $1$로 동일하며 www.acmicpc.net 문제 풀이 컨테이너의 높이 차이가 1까지 허용되기 때문에 평균 값을 중심으로 컨테이너를 재배치 해야겠다고 생각했다. 값들을 저장한 뒤 내림차순으로 정렬하고 정렬한 숫자에서 합을 n으로 나눈 뒤 나머지 만큼의 컨테이너는 1개가 더 쌓여있을 것이기 때문에 컨테이너를 빼냈다. 평균 컨테이너수보다 적거나 같은 컨테이너들은 앞쪽에서 빼낸 컨테이너들을.채워 넣는 것이기 때문에 break를 시켜줬..

• format_list_bulleted 알고리즘
• · 2023. 9. 23.

[백준] 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..

• format_list_bulleted 알고리즘
• · 2023. 9. 23.

[백준] 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이기 때문에 당연히 시간초과가 떠..

• format_list_bulleted 알고리즘
• · 2023. 9. 22.

[백준] 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보다 커서 상담이 불가능한지를 고려하여 코드를 작성했다. 남들이 작성한 코드가 시간이 적게 걸린 것 봐서는 다르게 짜는 ..

• format_list_bulleted 알고리즘
• · 2023. 9. 15.

[백준] 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; ..

• format_list_bulleted 알고리즘
• · 2023. 9. 14.