개발개굴🐸

[문제] [풀이] 이중탐색 + BFS를 사용하는 문제로 아래의 블로그를 참고하였습니다. https://hidelookit.tistory.com/200 [백준 1939] 중량제한 (자바) 백준 1939번 중량제한 (자바) 출처 www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤.. hidelookit.tistory.com left에 최소값 0을 삽입합니다. right 에 다리들중 가장 중량이 큰값을 넣어줍니다. (left + right)/2인 mid 값부터 해당 중량의 짐으로 섬-섬을 이동할수 있는지 확인하며, 만약 이동할수 있다면 mi..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net [문제] [풀이] 처음엔 "시작시간"기준으로 정렬후, 가능한 모든 회의 조합을 구하여 max값을 뽑아내려 했으나, 시간초과가 나왔습니다. 따라서 질문하기의 도움을 받아 "종료시간"기준으로 정렬하여 푸는 문제라는 힌트를 얻었습니다. - Compatable을 이용하여 종료시간으로 정렬하며, **만약 종료시간이 같다면 start시간이 짧은순서대로 정렬 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14 (1,4) -> time: 4 이므로 4보다 시작시간중 크거나 같은값이 나오면 ..

https://www.acmicpc.net/problem/2461 2461번: 대표 선수 입력의 첫 번째 줄에는 학급의 수를 나타내는 N과 각 학급의 학생의 수를 나타내는 M이 하나의 빈칸을 사이에 두고 주어진다. 단, 1 ≤ N, M ≤ 1,000이다. 두 번째 줄부터 N개의 줄에는 각 줄마다 한 www.acmicpc.net [문제 풀이] 처음엔 단순 조합을 통해 가능한 모든 조합을 계산하는 방식으로 풀이하였지만, 시간초과로 인해 다시 문제를 생각해보았습니다. 각각의 반의 선수의 능력치를 우선 정렬합니다. 투포인터 방식처럼 각 반의 index 0 부터 시작하여, 3개의 반중 최소값을 가지는 반의 index를 오른쪽 1 이동시키며 차이값을 구합니다. 12 12 16 16 16 43 43 67 67 67 ..

https://www.acmicpc.net/problem/2564 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net [문제 풀이] 각 방향별로 거리를 구할때 고려해야될 요소들이 많아서 다소 복잡했던 구현문제였습니다. 구현을 쉽게 하기 위해 왼쪽과 위쪽 경계로부터의 거리값을 북은 왼쪽, 동은 위쪽, 남은 오른쪽, 서는 아래쪽으로 거리를 저장했습니다. 그림으로 설명해 보자면 다음과 같습니다. shop배열에 상점 개수 만큼 방향값과, 위의 그림 방향 기준으로 거리값을 저장한 후 shop의 마지막 배열에 동근이의 방향값과 ..

https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net [문제 풀이] 이전에 풀었던 위상정렬을 사용한 백준 게임개발 문제랑 거의 비슷한 문제였습니다. 풀이는 게임개발 포스팅을 첨부하도록 하겠습니다. https://j-su2.tistory.com/4?category=1016202 [Java] 백준 1516번 - 게임 개발 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ..

https://www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net ---------------------------------------------------------------------------------------------------------------------- [문제 풀이] 문제가 엄청 길어서 복잡할줄 알았는데, 차근차근 읽어보니 단순 구현이라 생각보다 어렵지는 않았습니다. - start[]에 각 상..

https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net ---------------------------------------------------------------------------------------------------------------------- [문제 풀이] 이 문제는 특수알고리즘인 위상정렬을 사용해야 하는 문제였습니다. ( 위상정렬을 몰라서 한참 헤매다가 결국 풀이를 참고해서 풀었네요ㅠㅠ ) 아래의 블로그가 위상정렬..

https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net ---------------------------------------------------------------------------------------------------------------------- [문제 풀이] 각각의 칸을 기준으로 양옆으로 확장하여 최대 직사각형을 구한후, max값을 계속 갱신시켜주는 방법 풀이하였습니다. 예를 들어, 0번~6번의 블록..