본문 바로가기
카드 구매하기 2 - 백준 16194 (Java) https://www.acmicpc.net/problem/16194 풀이 DP 문제로, 규칙을 찾아보면 다음과 같다. i개 든 카드팩 vs (i-1)개 카드 최소 금액 + 1개 카드 최소 금액 vs (i-2)개 카드 최소 금액 + 2개 카드 최소 금액 ... vs (i+1)/2개 카드 최소 금액 + 나머지 카드 개수 최소 금액 이 중 최솟값이 dp[i] public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); StringTokenizer st = new.. 2022. 7. 24.
단어 맞추기 - 백준 9081 (Java) https://www.acmicpc.net/problem/9081 풀이 1. 뒤에서부터 바로 앞 요소와 비교한다. 1-1. 바로 앞 요소가 더 크거나 같으면 다음 요소로 넘어간다. 1-2. 바로 앞 요소가 더 작으면 아래 과정을 진행한다. 2. 바로 앞 요소를, 여태까지 지나왔던 요소들 중 바로 앞 요소보다 큰 수 중 최솟값으로 바꾼다. 3. 그 뒤는 오름차순으로 정렬 public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int totalCnt = Integer.parseInt(bf.readLine()); StringBu.. 2022. 7. 23.
안전 영역 - 백준 2468 (Java) https://www.acmicpc.net/problem/2468 풀이 지역의 높이에 해당하는 모든 값들만큼 각각 비가 왔다고 가정한다. 어느 높이만큼 비가 왔다고 가정했을 때, bfs 탐색으로 해당 경우에 몇 가지 안전 영역이 있는지 체크한다. main() //지역 높이 board static int[][] board; //각 지역의 높이값 저장할 set static Set set = new HashSet(); //각 bfs 탐색마다 false로 초기화 후, 방문 여부 체크할 배열 static boolean[][] isVisited; //board 사이즈 static int N; //row 방향 이동 배열 static final int[] DIRECTIONS_ROW = {-1, 0, 1 ,0}; //c.. 2022. 7. 22.
암호 만들기 - 백준 1759 (Java) https://www.acmicpc.net/problem/1759 풀이 해당하는 모든 경우에 대해 출력을 해야하므로 DFS 탐색으로 진행했다. main() static char[] alphabet; //모음 리스트 static List vowelList = new ArrayList(); static boolean[] isUsed; //최종 정답 기록하는 StringBuilder static StringBuilder sb = new StringBuilder(); //중간중간 임시로 기록하는 StringBuilder static StringBuilder tempSb = new StringBuilder(); public static void main(String[] args) throws IOException.. 2022. 7. 21.
톱니 바퀴 - 백준 14891 (Java) https://www.acmicpc.net/problem/14891 풀이 일단, 톱니 바퀴를 하나의 Integer list로 정의하고, 총 4개의 톱니 바퀴를 하나의 list에 저장했다. (gearList) 1번의 회전마다, 회전시키기 전에 현재 인접한 톱니 바퀴끼리 같은 극인지 체크해 boolean[]인 isSame에 저장했다. checkIfSame() public static void checkIfSame() { Integer first = gearList.get(0).get(2); Integer second = gearList.get(1).get(6); Integer third = gearList.get(1).get(2); Integer fourth = gearList.get(2).get(6); I.. 2022. 7. 17.
로마 숫자 - 백준 2608 (Java) https://www.acmicpc.net/problem/2608 풀이 1. 아라비아 문자를 숫자로 변환한다. 현재 문자와 바로 뒤 문자를 비교해서 각 문자에 해당하는 숫자가 뒤 문자가 더 크다면 (뒤 문자에 해당하는 숫자 - 현재 문자에 해당하는 숫자)를 더해준다. 나머지 경우는 현재 문자에 해당하는 숫자를 더해주면 된다. 2. 숫자를 아라비아 문자로 변환한다. 일단 현재 처리하고 있는 자릿수가 천의 자리인지 백의 자리인지 십의 자리인지 일의 자리인지에 따라 사용할 아라비아 문자가 정해진다. 즉, 다시 말해 각 자릿수에서의 1, 5, 10을 담당하는 아라비아 문자가 정해진다. 예를 들어 4에 대해서 백의 자리라면 CD, 십의 자리라면 XL, 일의 자리라면 IV가 된다. 각 자릿수에 해당하는 숫자에 따라.. 2022. 7. 12.
도로의 개수 - 백준 1577 (Java) https://www.acmicpc.net/problem/1577 풀이 먼저 아무 조건없이 격자 맵을 이동할 때 각 꼭지점마다 도달할 수 있는 경우의 수를 적어서 최종 목적지까지 도달하는 경우의 수를 구하는 방법을 생각했다. 이동 방향이 왼쪽 아래에서 오른쪽 위로 이동하기 때문에 현재 자신의 왼쪽 지점과 아래 지점까지 도달한 경우의 수의 합을 적어주면 된다. 여기서 이동할 수 없는 도로가 생겼을 땐, 해당 도로를 이동해야 자신에게 도착하는 경우의 수를 더하지 않으면 된다. 만일 왼쪽과 아래 점에서 오는 도로를 둘 다 이용하지 못할 경우 해당 지점에 도착하는 경우의 수는 0이 된다. 이를 코드에 옮기기 위해서, 꼭지점과 도로에 대한 정보를 담을 배열이 둘 다 필요했다. 그래서 꼭지점에 대한 이차원 배열 (.. 2022. 7. 10.
도서관 - 백준 1461 (Java) https://acmicpc.net/problem/1461 풀이 1. 일단 양수 위치와 음수 위치의 책을 분리해서 그룹을 지었다. 왜냐하면 어차피 한 그룹 안에 지정되어도 한 쪽 갔다가 되돌아와서 0을 지나 다시 반대 쪽으로 갔다가 돌아오기 때문에 그룹으로 지정하는 의미가 없기 때문이다. 2. 다음으로 고려한 부분은, 마지막에 모든 책을 제자리에 놔둔 후에는 0으로 돌아올 필요가 없기 때문에 절대값이 가장 큰 그룹을 마지막에 옮겨야한다. 3. 그리고 각 부호에서 가장 끝 수(가장 절대값이 큰 수)부터 그룹을 지었다. 예를 들면, 책이 3 6 8 20 25 위치에 있고 한 번에 옮길 수 있는 책이 2권이라 가정해보자. 만일 절대값이 가장 작은 수부터 그룹을 지으면 (3 6) (8 20) (25)가 된다. .. 2022. 7. 10.
회장뽑기 - 백준 2660 (Java) https://www.acmicpc.net/problem/2660 풀이 1. 회원들 간의 관계를 2차원 배열 그래프로 정리한다. 2. 한 회원마다 다른 회원과 친구가 되는 거리를 각각 구한다. 각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구사이이면서 동시에 친구의 친구사이이면, 이 두사람은 친구사이라고 본다. 문제의 조건을 보면 한 회원에서 다른 회원까지 도달하는 최단거리를 구해야 한다. 그러므로 bfs 알고리즘을 활용한다. 3. 2를 바탕으로, 한 회원을 기준으로 모든 회원과 친구가 되기 위한 최대 거리를 구한다. 4. 모든 회원들의 3번 값 중 최솟값을 가지는 회원을 찾는다. main() //회원들 간의 관계를 나타내는 그래프 static int[][] graph; public stati.. 2022. 6. 29.
숫자 고르기 - 백준 2668 (Java) https://www.acmicpc.net/problem/2668 풀이 문제 예시를 보면, 사이클1 : 1 -> 3 -> 1 사이클2 : 5 -> 5 인 경우가 정답에 해당 된다. 즉, 만들어지는 사이클에 속하는 숫자들을 출력하면 된다. 예시에서도 보면 알겠지만, 사이클은 재귀 방식으로 탐색할 수 있다. 사이클이 만들어지는지 탐색할 때 중간에 거치는 숫자들을 임시 리스트에 담았다가, 사이클이 만들어지면 임시 리스트에 담긴 값을 정답 리스트에 담는다. 어떤 한 숫자가 사이클에 속하게 되면 다른 사이클에는 속할 일이 없으므로, 사이클을 탐색할 때 정답 리스트에 없는 숫자로만 시작하면 된다. 재귀탐색 시 중단 조건은, 즉, 사이클을 이루는 조건은 탐색 중간값이 재귀탐색 시작점 값이 될 때이다. main() /.. 2022. 6. 24.

티스토리툴바