코딩테스트/백준

[백준]17073번 나무 위의 빗물 - Java

문제 https://www.acmicpc.net/problem/17073 17073번: 나무 위의 빗물 첫째 줄에 트리의 노드의 수 N과 1번 노드에 고인 물의 양을 의미하는 정수 W가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ W ≤ 109) 다음 N-1줄에 걸쳐, 트리에 존재하는 간선의 정보가 U V의 형태로 주어진다 www.acmicpc.net 풀이 처음엔 무슨 소린가 했는데 결국 리프 노드(자식이 없는 노드)의 수로 총 빗물의 양을 나눠주면 답이다! 그러므로 리프 노드를 어떻게 판별할지가 포인트인데, 트리에선 자신과 연결된 노드가 하나밖에 없는 경우가 리프 노드이다. (2개 이상이 연결되어 있으면 자식 노드가 존재하는 것이니까) 이 점을 이용하여 풀었다. 자세한건 주석으로! 코드 // 17..

[백준]2502번 떡 먹는 호랑이 - Java

문제 https://www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 풀이 피보나치 수열을 응용한 문제임 피보나치나 뭐 파도반 수열인가 이런거처럼 메모리가 초과될 위험이 있을 것 같다? 그럼 문제의 조건이나 문제를 잘 읽어서 대충이라도 시간복잡도를 계산해보고 괜찮겠다 싶으면 해야된다. 안 괜찮으면 DP 등으로 풀어야 됨. 이 문제는 순열에다가 피보나치 수열이라서 가지치기와 DP로 어떻게 푸냐가 포인트임! 3

[백준]4179번 불! - Java

문제 https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 풀이 며칠 전에 푼 '탈출'이라는 문제랑 완전 비슷하다!!! https://seokmimmmmmmmm.tistory.com/123 [백준]3055번 탈출 - Java 문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 ..

[백준]14499번 주사위 굴리기 - Java

문제 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 풀이 시뮬레이션 문제이다. 주사위를 어떻게 굴릴지만 구현하면 된다! 나는 주사위 전개도를 2차원 배열로 보고 동서북남 방향으로 굴릴 경우, 어떻게 전개도가 바뀔지 생각해서 구현했다. 1차원 배열 2개로 전개도를 구현하거나, 클래스를 만들어서 주사위의 윗면, 아랫면, 앞면, 뒷면, 왼쪽면, 오른쪽면을 구현해도 같은 결과를 얻을 ..

[백준]3055번 탈출 - Java

문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 bfs 문제임! 주의할 점은 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 이렇기 때문에 물을 먼저 bfs로 퍼지게 하고 그 후에 고슴도치를 bfs로 이동시켜야 한다! 나는 큐를 두개 만들어서 풀었지만 큐 하나로도 가능할 것 같다!! 자세한건 주석으로! 코드 // 3055번..

[백준]1743번 음식물 피하기 - Java

문제 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 풀이 걍 흔한 dfs나 bfs 문제이다! 나는 dfs로 풀었음! 정답은 음식물 쓰레기의 최대 크기이므로 static 변수로 선언해서 dfs한번이 끝나면 음식물 쓰레기의 크기를 측정하여 최신화해주는 방식을 사용했다. 자세한건 주석으로! 코드 // 1743번 음식물 피하기 // https://www.acmicpc.net/problem/1743 packag..

[백준]5212번 지구 온난화 - Java

문제 https://www.acmicpc.net/problem/5212 5212번: 지구 온난화 첫째 줄에 지도의 크기 R과 C (1 ≤ R, C ≤ 10)가 주어진다. 다음 R개 줄에는 현재 지도가 주어진다. www.acmicpc.net 풀이 그냥 이차원 배열 돌면서 3면 이상이 바다면 땅을 물에 잠기게 해주면 된다. 새로운 정답 2차원 배열 지도를 만들어서 물에 잠긴 땅이 다음 칸에도 영향을 주지 않게 하였음! 정답 지도를 그릴 때는 다시 정답 배열을 돌면서 범위 체크를 위한 변수를 최신화하고 그 범위 내의 지도만 그려줌! 위의 두 가지만 조심하면 어렵지 않게 금방 풀 수 있는 문제임!!! 자세한 건 주석으로!! 코드 // 5212번 지구 온난화 // https://www.acmicpc.net/pro..

[백준]11559번 Puyo Puyo - Java

문제 https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 풀이 처음에 어떻게 풀지 설계를 안하고 풀다보니까 중간에 한번 엎었다... 문제 좀 똑바로 읽고 풀자 쫌...!!!!! 쭈욱 돌면서 뿌요가 있으면 같은 색의 뿌요가 4개 이상 인접해있는지 dfs()로 판단하다가 4개가 넘어가면 그 위치에서 다시 dfsBomb()를 돌려서 연결되어 있는 뿌요를 다 없앰! 그리고 다른 색의 뿌요도 4개 이상이 인접해 있는 경우가 있으니까..