6-6화이탱

https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 오랜만에 dp문제를 풀게 되어서인지 많이 헤맸다...ㅜㅠㅠ 간단해보이면서도 생각해내기 어려운 문제였다. dp[0][n-1] 은 0~n-1까지의 행렬의 곱셈값을 넣은 것을 뜻한다. 포문을 돌면서 아래의 과정으로 계산을 한다. dp[i][i+k] = Math.min(dp[i][i+k], dp[i][j]+dp[j+1][i+k] + arr[i][0]*arr[j][1]*arr[i+k][1]);..

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 이 문제는 유니온 파인드를 사용하면 쉽게 해결할 수 있었다! https://brenden.tistory.com/33 [알고리즘] 유니온 파인드 (Union-Find) 유니온 파인드(Union-Find) ① 유니온 파인드란? ▷ 대표적 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있습니다.▷ 상호 배타적 집합(Disjoint-set)이라고도 합니다.▷ ..

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 학생 리스트 큐 1 자리 배열 1 x,y 배열 각 1 1. 최대한 많은 좋아하는 학생들과 인접한 자리 2. 비어있는 인접한 자리 수 3. 작은 열 세가지의 조건으로 자리를 배정한다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Array..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 전체적인 배열 1 사각지대 현황 배열 1 cctv 위치 리스트 1 dfs로 모든 cctv의 각도에 따른 사각지대를 확인한 후 최소값을 출력한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.uti..

https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 살아 있는 나무의 정보를 넣을 디큐 1 죽은 나무 정보 큐 1 겨울에 보충될 양분 배열 1 현재 양분 배열 1 x,y 배열 각 1개씩 선언하여 문제를 풀었다. 주의할 점은 같은 공간의 나무들중에 가장 나이가 어린 나무 먼저 양분을 흡수 하는 것인데, 이를 위해서 Collections.sort 로 정렬을 하게되면 시간초과가 발생한다. 따라서 Deque의 addFirst로 번식된 나무..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 처음에 BFS로 접근하여 풀었다가 시간초과가 발생하여 DFS로 다시 풀게된 문제이다. 방문한 배열, 팀 구성 완료된 배열을 생성하여 포문을 돌면서 확인한다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 다른 방식으로 접근했다가 많이 헤맸다... 완전탐색으로 풀어야하는 문제였다.. 최대 N이 500,000임으로 6글자의 가장 큰 수인 999,999까지 포문을 돌려서 해당 숫자일 경우의 이동 수를 세어준다! 고장난 버튼의 숫자가 있을 경우에는 그냥 다음 숫자로 넘겨버린다!! import java.io.BufferedReader; import java.io.IOException; im..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 이 문제를 풀기 전에 아래의 문제를 푸시는 것을 추천드립니다! https://iheeeee6-6.tistory.com/21 [백준 7576] 토마토 풀이 (JAVA) https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타..

https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 처음에는 0인 곳들을 큐에 넣어 bfs로 탐색하였는데, 알고보니 막혀있는 공기는 제외해야하는 것이었다. 따라서, (0,0)부터 탐색을 하여 0이면 큐에 넣고 1이면 잠시 2로 바꿔준 후, 다 진행한 후에 2로 된 것들을 0으로 바꿔준다. 탐색을 할때는 check배열을 통해 첫 방문지인지 확인하여 탐색한다. import java.io.BufferedReader; import java.io.IOException; imp..

https://www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 주유소 정보는 거리순으로 주어지지 않기 때문에 우선순위 큐에 정보를 넣고 오름차순 정렬하였다. 현재 연료로 갈 수 있는 주유소까지의 최대 기름을 큐에 넣고는 하나씩 꺼내서 나아간다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import ..