6-6화이탱

https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net dp를 사용하여 이중 포문을 돌려서 자신의 번호보다 앞에 있는 숫자 중에서 자신보다 작은 숫자의 개수를 dp에 넣는다. 이때, 그 작은 숫자의 dp값 +1과 내 번호의 현재 dp값 중에 더 큰 값을 dp에 넣는다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.uti..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 점화식을 생각해내지 못해서 어려웠던 문제였다ㅠㅠ 1 2 3 4 5 6 7 8 만약 위와 같은 스티커 배열이 있다면, 7번은 1번과 2번 중 더 큰 값을 선택하면 된다! 마찬가지로 3번은 5번과 6번 중 더 큰 값을 선택하면 된다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRea..

https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 처음에는 재귀함수를 썼더니 시간초과가 났다.. 포문을 돌려서 dp의 값을 더해준다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int arr[][]; sta..

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/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은 상자의 세로 칸의 수를 나타..