박카스러버

https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 먼저 저는 처음에 이분탐색을 생각하고 문제풀이를 진행하였습니다. 계속 틀리길래 문제를 다시 보니 마지막 줄의 '수의 위치가 다르면 값이 같아도 다른 수이다.'의 의미를 이해하였습니다. 3 0 0 0 다음과 같이 입력이 들어온다면 결과값이 3이 나와야합니다. 또한 이분 탐색으로 하게 되면 같은 수가 존재하면 같은 수 중에 어떤 인덱스를 줄지 모릅니다. 그래서 저는 해당 문제를 Map을 이용하여 문제를 해결하였습니다. Map을 ..

https://www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 저는 해당 문제를 BFS를 이용하여 문제를 해결하였습니다. 일반적인 체스의 나이트와는 다르게 이동해서 조금 헷갈리는 문제였습니다. package BOJ.BFS; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays;..

https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 저는 DP를 이용하여 문제를 해결하였습니다. A -> B B -> BA 이렇게 되므로 점화식을 a[n] = b[n-1] b[n] = a[n-1] + b[n-1] 이렇게 세워서 해결하였습니다. package BOJ.DP; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java...

https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 저는 해당 문제를 BFS를 통해 한 자리씩 변경하면서 몇번만에 해당 숫자로 변하는지 확인하였습니다. isPrime을 통해 1000 ~ 9999까지 해당 숫자가 소수인지를 파악하였고 1000 전까지의 숫자는 false를 줌으로써 BFS에 들어가지 못하게 처리하였습니다. package BOJ.BFS; import java.io.BufferedReader; import java.io.InputStreamRead..

https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1≤N≤1,000)과 도로의 개수 M(1≤M≤n*(n-1)/2) 이 주어진다. 입력의 두 번째 줄 www.acmicpc.net 저는 프림 알고리즘을 사용하여 문제를 해결하였습니다. 하나는 프림을 가장 짧은 것을 추적하도록 하였고, 하나는 가장 긴 것을 추적하도록 작성하여 문제를 풀었습니다. package BOJ.MST; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import j..

https://www.acmicpc.net/problem/1949 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,00 www.acmicpc.net 저는 해당 문제를 DP를 이용하여 문제를 해결하였습니다. dp[node번호][0] : node번호를 우수마을로 선정하지 않을 때의 최대 우수 마을 인원 수 dp[node번호][1] : node번호를 우수마을로 선정했을때의 최대 우수 마을 인원 수 package BOJ.DP; import java.io.BufferedReader; import java.io.InputStream..

https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 저는 해당 문제를 DP를 이용하여 문제를 해결하였습니다. dp[노드 번호][0] : 해당 노드를 얼리어덥터로 설정하지 않는다. dp[노드 번호][1] : 해당 노드를 얼이어덥터로 설정한다. 만약 현재 노드가 얼리어덥터가 아니라면 자식들은 모두 얼리어덥터여야하며, 만약 현재 노드가 얼리어덥터라면 자식이 얼리어덥터와 얼리어덥터가 아닌 것을 선택할 수 있다. dp[now][0] += dp[next..

https://www.acmicpc.net/problem/9470 9470번: Strahler 순서 지질학에서 하천계는 유향그래프로 나타낼 수 있다. 강은 간선으로 나타내며, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 호수나 샘처럼 강이 시작하는 곳, 강이 합쳐지거나 나누어지는 곳 www.acmicpc.net 저는 해당 문제를 위상정렬을 응용하여 문제를 해결하였습니다. count배열를 통해 해당 노드를 Queue에 넣을라면 몇번 방문해야하는지를 체크했습니다. number배열을 통해 해당 노드에 가장 큰 Strahler을 저장하였습니다. isNumber는 해당 number배열에 있는 값이 한번 들어왔는지 두번 들어왔는지를 체크하였습니다. 이를 통해 Queue에 넣을 때 isNumber가 true거나 ..

https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 저는 해당 문제를 4차원 boolean 배열과 BFS를 통해 해결하였습니다. 저는 문제를 조금 더 쉽게 해결하기 위해 더미 행 열을 상하좌우에 하나씪 추가하였습니다. 이를 통해 떨어졌는지는 좌표가 0이나 끝에 있는지를 확인하여 판별하였습니다. 저는 처음에 둘 다 드랍되면 해당 좌표는 BFS를 진행하면 안 되는 히든 룰(?) 적용시키지 않아서 테스트 케이스에서 잘못된 결과가 나왔습니다. packa..

https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 저는 해당 문제를 dfs를 이용해 문제 예시의 역순으로 각각의 숫자들이 소수인지를 판별하였습니다. 예를 들어 7331이라면 7이 소수인지 확인하고 73이 소수인지 ... 이렇게 왼쪽의 숫자부터 확인하였습니다. 이유는 중복때문이였습니다. 오른쪽에서 처리하게된다면 7331에서 7이 소수인지 확인하고 7332에서도 확인하게 됩니다. 그래서 가장 높은 자리부터 소수라면 dfs의 depth를 들..