백준

[BJ] 백준 15591 MooTube (Silver) (JAVA)

문제 https://www.acmicpc.net/problem/15591 풀이 방법 이 문제는 시간초과가 관건인 문제였다. 처음에는 인접 행렬로 풀이를 하려고 했는데 계속해서 시간초과가 발생했다. 그래서 도저히 시간을 단축시킬 방법이 생각이 안나서 찾아봤더니 인접 리스트를 사용하면 풀리는 문제였다. 풀이 과정은 다음과 같다. 1. 인접 리스트를 생성해서 인접한 정점들과 USADO 값을 저장해준다. 2. v번째 정점으로부터 BFS를 시작한다. 3. queue에서 poll를 한 정점(n)과 인접하고(USADO값이 존재) 방문하지 않은 정점들만 탐색 후보가 된다. 4. n번 정점과 탐색 후보 사이의 USADO 값이 k이상인 경우에만 que에 넣어준다. 5. 그리고 cnt도 하나 증가해준다. 왜냐면 visit배..

[BJ] 백준 11047 동전 0 (JAVA)

문제 https://www.acmicpc.net/problem/11047 풀이 방법 대표적인 그리디 알고리즘 문제이다. 동전의 단위가 있고, 금액이 있을 때 금액을 만들 수 있는 동전의 최소 개수를 구하면 된다. 순서는 정렬을 하고 단위가 큰 순서대로 금액에서 차감하면 되는데 입력값이 오름차순으로 주어진다고 했으니까 따로 정렬하지 않고 뒤에서부터 금액을 차감해주는 식으로 구현했다. 그리고 몫이 없으면 점점 단위가 내려가고 동전이 0이 되는 경우 for문을 벗어날 수 있게 해줬다. 제출 코드 import java.io.*; public class BOJ_11047_동전0 { public static void main(String[] args) throws IOException { BufferedReader..

[BJ] 백준 21610 마법사 상어와 비바라기 (JAVA)

문제 https://www.acmicpc.net/problem/21610 풀이 방법 문제에 따라서 순서대로 차근차근 구현해갔다. 문제에서 주목해야할 점은 1. 구름이 이동할 때 범위에 신경써야 하는 것 2. 대각선 방향을 확인할때의 범위는 또 다르게 적용된다는 것 3. 한꺼번에 처리하려다가 오히려 잘못된 값이 나올 수 있다는 점 이 세가지인 듯 하다. 나는 구현하는 건 어렵지 않았지만 3번 때문에 디버깅하는데 조금 시간이 걸렸다. 그리고 격자도 그렇고, 방향도 그렇고 인덱스 1부터 시작하는걸 나는 0부터 시작하는 걸로 수정해서 구현했다. 전제적인 과정을 정리하면 다음과 같다. 1. 처음에 구름 생성해주기 2. M번 이동 실행하기 1) 모든 구름을 올바른 방향으로 이동 시키기 2) 물의 양 증가시키기 3)..

[BJ] 백준 2193 이친 수 (JAVA)

문제 https://www.acmicpc.net/problem/2193 풀이 방법 이 문제도 dp문제다. 0과 1로만 이루어진 수를 이진수라고 하며, 다음과 같은 성질을 만족하는 수를 이친수라고 한다. 1. 0으로 시작하지 않는다. 2. 1이 연속해서 두번 나타나지 않는다. N자리 이친수의 개수를 구하면 된다. 2차원 dp배열을 사용해서 풀이했다. dp[N][0]에는 N자리 수이며 마지막 수가 0인 이친수의 개수, dp[N][1]에는 N자리 수이며 마지막 수가 1인 수의 개수를 저장해줬다. 그리고 이제 반복문을 돌면서 끝자리가 0인 경우에는 1과 0 모두 다 올 수 있으므로 dp[i+1][0], dp[i+1][1] 에 모두 dp[i][0]의 값을 더해줬다. 그리고 끝자리가 1인 경우에는 연속으로 1이 두..

[BJ] 백준 10163 색종이(JAVA)

문제 https://www.acmicpc.net/problem/10163 풀이 방법 이 문제는 서브태스크로 채점이되는 문제이다. 서브태스크 문제는 약간 예외를 생각하기 좋은 것 같다. 문제를 간단하게 설명하자면 여러장의 색종이를 순서대로 놓는데 겹쳐서 놓을 수가 있다. 출력값으로 색종이를 다 놓았을 때 각각의 색종이가 보이는 면적을 출력해야한다. (https://yoon990.tistory.com/33 이 문제가 생각이 났다.) 그래서 위에서 언급한 문제를 응용해서 이번에는 무조건 1로만 채우는 것이 아니라 색종이의 번호를 넣어주는 식으로 생각을 했다. 첫번째 색종이 면적은 1로, 2번째면 2로 .. 이런식으로 N번째 색종이까지 다 채운 후, 마지막에 1부터 N까지 map에 자신에 해당하는 번호가 몇 개..

[BJ] 백준 2628 종이자르기 (JAVA)

문제 https://www.acmicpc.net/problem/2628 풀이 방법 우선 행과 열의 크기에 맞게 1차원 배열을 선언해줬다. 그리고 그 배열에는 입력에 따라서 자른 점선 번호이면 1로 배열 값을 수정해줬다. 문제와 같은 예시로 설명을 하자면 num 1 2 3 4 5 6 7 8 9 cutM 0 0 0 1 0 0 0 0 0 num 1 2 3 4 5 6 7 cutN 0 1 1 0 0 0 0 이런식으로 값이 들어가게 된다. 그 후 이제 각각 배열을 돌면서 temp 길이를 1을 하나씩 추가하다가 1을 만나면(잘려진 선을 만났으므로) 최대 길이와 비교해서 필요시 최대길이를 업데이트해주고 temp는 다시 0으로 설정해준다. (새로운 길이 시작) 열과 행을 같은 방법으로 구현 후, 각각의 max값을 곱해주..

[BJ] 백준 2635 수 이어가기 (JAVA)

문제 https://www.acmicpc.net/problem/2635 풀이 방법 첫 번째 수를 입력으로 받고 두번째 수를 선택한 뒤 세번째 부터는 앞에 두 개의 숫자를 빼면서 하나씩 새로운 수를 만들어가는 문제이다. 1. N 부터 1 까지 하나씩 두번째 수로 선택 한다. 2. 음수가 나올때까지 while문에서 세번째 수 부터 하나씩 만들면서 list에 추가한다. 3. 하나의 list가 만들어질 때마다 최대 크기를 비교해서 업데이트하고, 업데이트가 되는 경우엔 배열도 같이 복사해준다. 3. 마지막엔 최종적으로 max에 담겨있는 개수와 list를 출력해줬다. 제출 코드 import java.io.*; import java.util.*; public class BJ_2635_수이어가기 { public sta..

[BJ] 백준 15683 감시 (JAVA)

문제 https://www.acmicpc.net/problem/15683 풀이 방법 cctv의 종류에 따라서 탐색해야하는 방향이 다른 문제이다. cctv가 탐색할 수 있는 공간을 다 탐색 후 cctv가 탐색하지 못한 사각지대를 찾아내면 된다. 복잡하긴 하지만 정리해서 구현만 한다면 그렇게 어렵지는 않은 문제다. 1. 클래스를 하나 만들어서 cctv의 종류에 따라서 탐색해야하는 인덱스를 미리 저장해놨다. 2. cctv의 종류에 따라서 방향이 다르기도 하지만 탐색 횟수도 다르다는걸 주의해야한다. ex) 1번은 90씩 회전해서 4번 탐색이 가능하지만, 2번은 2번만 탐색한다. 3. 탐색을 하면 나는 #으로 배열을 변경해줬고, 나중에 사각지대를 계산할 때는 0인 것들을 찾아서 카운팅 한 후 출력해줬다. 제출 코..

[BJ] 백준 1244 스위치 켜고 끄기 (JAVA)

문제 https://www.acmicpc.net/problem/1244 풀이 방법 스위치의 상태를 바꿔주는 문제이다. 여학생인지 남학생인지 판단 후에 남학생이라면 해당 번호의 배수에 해당하는 인덱스를 가진 스위치를 토글해주고, 여학생이라면 해당 번호의 스위치를 우선 변경 후 , -1 +1를 위치에 있는 스위치가 같은지 여부를 판단 후, 같다면 토글해주고 같지 않다면 토글하지 않는 식으로 구현했다. 제출 코드 import java.io.*; import java.util.*; public class BJ_1244_스위치켜고끄기 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(..