본문 바로가기
반응형

Problem Solving155

백준 15683 : 감시 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net [ 문제풀이 ] 전형적인 시뮬레이션 문제이다. 감시 카메라가 가능한 모든 경우의 수를 돌려보면 쉽게 해결할 수 있다. ​모든 감시 카메라의 경우의 수를 구하고 감시 영역을 체크하는 부분을 각각 구현한다면 코드가 상당히 난잡해질 것이다. 1~5번 CCTV가 가능한 경우의 수가 그렇게 많지 않기 때문에 미리 배열로 어느 정도 선언한 후 구현한다면 코드도 간결해지고 구현하기가 더욱 쉬울 것이.. 2021. 8. 2.
백준 14891 : 톱니바퀴 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net [ 문제풀이 ] 전형적인 시뮬레이션 문제로써 정말 쉬운 문제이다. 회전할 톱니바퀴를 기준으로 좌우 측의 톱니바퀴의 회전 유무를 체크해 준 후 각 톱니바퀴를 회전시켜주기만 하면 간단하게 해결할 수 있다. ​톱니바퀴를 다음과 같이 1차원 배열로 관리하자. check라는 1차원 배열을 선언한 후 회전할 톱니바퀴를 기준으로 2, 6번 인덱스의 값을 비교해 주면서 회전이 가능한지, 가능하다면 시계(1.. 2021. 8. 2.
백준 14890 : 경사로 https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net [ 문제풀이 ] 모든 행/열을 돌면서 경사로를 놓을 수 있는지를 확인하면 되는 문제이다. 경사로를 놓는 조건이 조금 까다롭기 때문에 난이도가 조금 있는 것 같다. ​행/열을 확인하는 함수를 2개 구현하지 말고 1방향으로 통일하자. 행을 열로 바꿔준다면 열을 확인하는 함수 1개만 구현해 주면 훨씬 편할 것이다. ​경사로를 놓을 수 있는지 판단하는 조건은 총 3개이다. 이를 편하게 관리하기 위해 현재 사용할 수 있는 거리를.. 2021. 8. 2.
백준 14889 : 스타트와 링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net [ 문제풀이 ] 간단한 문제이다. N명의 사람 중 N/2명의 사람을 뽑는 조합을 구현할 수 있다면 아주 쉽게 해결할 수 있는 문제이다. ​다만, 모든 조합을 구할 필요가 없다. 6명의 사람 중 3명을 뽑는 모든 조합을 한번 보자. 자세히 보면 1번 사람을 선택한 후 가능한 조합 이후로는 이미 앞에서 구한 조합들만 나오는 것을 확인할 수 있다. 따라서 우리는 모든 조합을 구할 필요 없이 1번 사람을 포함하는 조합만 구하.. 2021. 8. 2.
백준 14888 : 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net [ 문제풀이 ] 간단한 문제이다. 주어진 연산자로 만들 수 있는 모든 경우의 수를 다 탐색하여 최댓값과 최솟값을 구해주면 된다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamRead.. 2021. 8. 2.
백준 14503 : 로봇 청소기 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net [ 문제풀이 ] 간단한 시뮬레이션 문제이다. 주어진 조건 그대로 로봇을 움직이도록 구현하면 쉽게 해결할 수 있을 것이다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWri.. 2021. 8. 2.
백준 14502 : 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net [ 문제풀이 ] 이번에도 간단한 시뮬레이션 문제이다. 0인 공간에 벽을 세우면서 3개를 세웠을 경우 바이러스를 퍼트려 안전 공간의 개수를 카운트해 주면 쉽게 해결할 수 있다. ​벽을 3개 세우는 경우의 수를 구하는 것은 백트래킹 기법을 통해 구하면 될 것이다. ​나는 처음에 Virus라는 클래스를 구현하여 바이러스들을 관리해줬는데 매번 새로운 바이러스 객체를 생성해주는 것은 메모리에 부담이 크다. 어차피 바이.. 2021. 8. 2.
백준 4195 : 친구 네트워크 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net [ 문제풀이 ] 두 친구가 같은 그래프에 속하는지를 판단해야 하기 때문에 Union-Find 알고리즘을 활용하면 해결할 수 있다. 다만, 매번 두 친구가 속한 그래프의 정점의 개수를 탐색한다면 시간 초과가 발생할 것이다. 이를 위해 rank 배열을 하나 선언하여 각 정점마다 자식의 수를 관리해주도록 한다. 두 친구를 union할때 자식의 수가 많은 친구를 부모로 두 친구를 합해준다. i.. 2021. 8. 2.
백준 15486 : 퇴사 2 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net [ 문제풀이 ] 다이나믹 프로그래밍을 이용한 정해의 시간 복잡도가 O(N)이었기 때문에 다시 한번 풀어봤다. 퇴사 1을 해결한 나의 코드에서 어떤 부분을 줄일 수 있을지 생각해봤다. ​아래의 코드가 퇴사 1에서 O(N^2)의 시간 복잡도를 가지는 구간이다. for (int i = 2; i = 0) { dp[i] = Math.max(dp[i], dp[j] + P[i]).. 2021. 8. 1.
반응형

티스토리툴바