IT recording...

https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net [풀이] 양팔 저울의 양쪽에 올릴 수 있는 모든 추의 조합을 구해서 O(N^4)로도 할 수 있겠지만 그건 당연히 시간 초과일 것.. 끙끙대다가 풀이를 보았고 dp를 이용해서 푸는 문제라는 것을 알게 되었다. dp = boolean[N+1][30001]; //n번째 추를 올려놓았을 때 만들 수 있는 추의 무게에 true를 표시한다. -> 예를 들어 (왼쪽) 추+a+b = c+d+e+f (오른쪽) =>..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net [풀이] 사방으로 이동하면서 연결된 집들의 갯수를 구하는 문제 1. 집들을 모두 ArrayList에 넣어두고, 방문하지 않은 집을 모두 방문하며 dfs를 들어간 횟수를 구한다. (answer) 2. 하나의 집단 탐색이 끝났을 때 총 몇 번 지나왔는지 세기 위해서 전역변수로 count를 두고 새끼dfs를 들어갈 때마다 증가시킨다. 그리고 하나의 집단 탐색이 끝나면 queue에 add (오름차순으로 정..

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net [풀이] 문제를 보고 키보드를 잡기까지 상당한 시간이 걸렸다. 어떻게 풀이 방법을 생각해야할지를 모르겠었기 때문이다 처음에는 다음과 같이 생각했다. 홀수개의 사다리 선이 있으면 i -> i 제자리로 돌아올 수 없으므로 홀수인 애들한테 가서 dfs를 돌리면 되지 않을까? 그래서 짝수인 경우는 사다리를 놓지 않고, 홀수인 경우에만 하나씩 놓아서 문제를 해결하려 해보았다. 그런데 테케는 다 맞았지만 ..

[원문링크] https://adorable-aspen-d23.notion.site/BOJ-2573-fd58e2125704471dbe1e295133cc8926 [BOJ] 2573 빙산 코드 adorable-aspen-d23.notion.site 2573번: 빙산 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net [풀이] 처음에는 union-find로 부모를 관리해야 하는 건 줄 알았는데 하다보니 점점 미궁속으로 빨려들어갔다. 이에 답을 참고하기로 결정 ㅠㅠ 답을 보고 dfs를 활용한 단절점 문제와 비슷한 방..