[백준] 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 문제 풀이 맨 처음에 문제를 보자마자 누적합 배열을 만들어야하나 라고 생각했는데, 어떤식으로 풀어야 할지 모르겠어서 완전 탐색 방식으로..

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

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