본문 바로가기

알고스팟17

[종만북] CHILDRENDAY - 어린이날 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-CHILDRENDAY 풀이 만약 특정 자릿수(D)만을 포함하여 만든 십진수에 대해 N으로 나누어 떨어지는 가장 작은 수를 구하는 문제가 있다고 해보자. 이 경우 웰-논한 방법이 있는데, 나머지 연산의 성질을 이용하면 된다. 사용할 수 있는 자릿수가 '1, 2, 3'일 경우 1을 뒤에 붙이는 경우, 2를 붙이는 경우, 3을 붙이는 경우가 있을 것이다. 이런식으로 해보면 다음과 같이 진행될 것이다. 각 단계마다 진행하다가 N으로 나눈 나머지가 0일 경우 멈추면 된다. 이 때 구하려는 수를 C라 할 때, C는 엄청 커다란 수가 될 수 있다. 대충 N이 10000이므로 총 1만자리까진 가능 할 것같다. 따라서 이걸 큰 수로 계산하게 되면 시.. 2023. 7. 17.
[종만북] SORTGAME - Sorting Game (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-SORTGAME 풀이 우선 생각해야 할 부분은, '한 수열에 같은 수가 두 번 출현하지 않는다고 가정해도 좋다. 모든 수는 1부터 1백만 사이의 정수' 라는 지문 부분이다. 1부터 1백만 사이로 입력이 들어오는게 의미가 있을까? 어차피 대소 관계 순서만 동일하다면 전혀 상관 없다. 따라서 값 압축을 통해 1부터 N까지의 값으로 우선 압축해서 생각하자. 예를들어 N개가 '1000000 4 2 5000' 이렇게 들어왔다면, 압축해서 '4 2 1 3'와 같이 생각하면 된다. 또한 N은 최대 8 이므로, 정수 하나로 표현할 수 있다. 즉 위의 '4 2 1 3'은 '4213'에 해당한다. private int compressedNum(int .. 2023. 7. 17.
[종만북] GRADUATION - 졸업 학기 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-GRADUATION 풀이 dfs나 bfs로 풀 수 있는 문제이다. 상당히 구현하기 까다로웠던 것 같다. 풀이는 주석으로 대신하는게 더 이해하기 좋을 것 같다. ... private void solution() throws Exception { StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int l = Integer.parseInt(st.nextToken().. 2023. 5. 15.
[종만북] JOSEPHUS - 조세푸스 문제 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-JOSEPHUS 풀이 문제에서 제시된 방식대로 시뮬레이션을 돌려도 통과되는 문제이다. 실제로 2개가 남을 때 까지 List에서 제거하는 방식으로 시뮬레이션을 돌려서 풀었다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)).. 2023. 5. 15.
[종만북] MATCHORDER - 출전 순서 정하기 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-MATCHORDER 풀이 생각해야 할 조건은 두 가지이다. 1. 러시아와 한국 팀이 1:1로 매칭이 되긴 해야 한다. 2. 러시아팀의 레이팅 이상이기만 하다면 그 차이는 무시할 수 있다. 위 두가지를 생각하면서 최대한으로 이기려고 한다면, 각 러시아팀 레이팅에 대해 최대한 차이가 적은 그 이상의 한국팀 레이팅을 매칭시켜주면 된다. 또한 1:1로 매칭되긴 해야하므로, 현재 러시아팀 레이팅 이상의 값이 남는게 없다면 남은 한국팀 레이팅 중 가장 낮은 값을 매칭해준다. 현재 러시아의 레이팅 이상이면서 가장 작은 값은 이분 탐색으로 찾도록 구현했다. 코드 : github import java.io.BufferedReader; import j.. 2023. 4. 17.
[종만북] STRJOIN - 문자열 합치기 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-STRJOIN 풀이 N개의 문자열이 주어질 때, 여기서 2개를 선택해 새로운 문자열을 만들고, 그 길이의 합이 비용이 된다. 이걸 하나의 문자열만 남을 때 까지 반복하는 문제이다. 합치는 순서가 중요할텐데, 4개의 문자열이 있고 각 길이가 A, B, C, D라고 해보자. (A)와 (B)를 합치면 (A+B)의 문자열이 된다. 그럼 문자열은 현재 (A+B), (C), (D)가 있다. (A+B)와 (C)를 합치면 (A+B+C)가 된다. 그리고 다시 (D)와 합치면 (A+B+C+D)가 된다. 여기서 비용에 들어간 횟수를 살펴보면 'A'와 'B'는 비용에 총 3번, 'C'는 2번, 'D'는 1번 더해졌다. 따라서 직관적으로 여러번 합쳐질 녀석.. 2023. 4. 14.
[종만북] LUNCHBOX - Microwaving Lunch Boxes (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-LUNCHBOX 풀이 N개의 Lunch Box가 있고, 각각 전자렌지에 돌리는 시간 M과 먹는시간 E를 가지는 상황이다. 여기서 고정인 부분은 전자렌지 돌리는 시간 M는 무조건 N개의 M을 전부 더한 시간만큼이 필요하다. 반면에 먹는시간 E는 각 M이 끝날때마다 시작된다. 예를들어 아래와 같은 입력을 보자. 1 3 1 3 2 10 4 1 순서대로 진행해본다면 아래와 같이 진행된다. 사실 저 순서대로 처리하는게 풀이인데, 결국 M의 총합은 항상 고정이고, E가 시작하는건 각 M이 끝난 이후이므로 E가 긴 녀석을 최대한 빨리 먹기 시작해서 처리하는게 무조건 이득이다. 따라서 E값 내림차순으로 정렬한 후 (E가 동일할 시 M을 내림차순으로.. 2023. 4. 14.
[종만북] POLY - 폴리오미노 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-POLY 풀이 문제에서 제시된 규칙은 결국, 세로야 어떻든 가로로 선을 그었을 때 빈 곳이 있으면 안되고 또 전부 붙어있어야한다는 의미가 된다. 따라서 n개를 행 1개~행 n개 에 걸쳐 각 행에 몇 개씩 배치할 것인지로 바꿔서 생각하면 된다. 그리고 2개의 행을 봤을 때, 두 행에 대해 만들 수 있는 경우의 수는 '행1의 블록 수 + 행2의 블록 수 - 1' 이 된다. 예를들어 각 행에 3개씩 배치했을 경우 나올 수 있는 경우의 수는 3+3-1 = 5 이다. 아래 경우들과 같다. 따라서 각 행별로 현재 남은 블록의 수를 '1개부터 남은 블록의 수'로 배치하면서 위에서 얘기한 경우의 수를 바로 직전 행의 블록수와 함께 계산해보면 된다... 2023. 4. 10.
[종만북] NUMB3RS - 두니발 박사의 탈옥 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-NUMB3RS 풀이 예제 입력의 첫 번째 테스트케이스를 그래프로 그려보면 아래와 같다. 탈출 전 확률이 1(100%)이라 한다면 이후 간선을 따라, 간선이 존재하는 만큼 확률이 나뉘어져서 들어가게 된다. 탈출 전일 때 0에서 시작하므로 0은 1로 시작하고, 탈출 1일차에 0에서 갈 수 있는 간선이 1,2,3 이므로 1/3씩 나뉘어 들어간다. 그리고 2일차에 1과 3에 있던 1/3은 0으로 다시 돌아오고, 2에 있던 1/3은 0과 4로 1/6씩 나뉘어 들어가게 된다. 따라서 2일차에 0에 위치는 5/6, 1,2,3 위치는 0, 4는 1/6이 된다. 이런식으로 일차별로 계속 진행한 후 q에 따라 출력해주면 된다. 코드 : github i.. 2023. 4. 10.
[종만북] ASYMTILING - 비대칭 타일링 (자바 java) 알고리즘 문제해결전략(종만북) 스터디 메인 페이지 목차 문제 : aoj-ASYMTILING 풀이 일단 대칭인 경우는 생각하지 않고, 2xn 타일링부터 생각해보자. dp[x]를 x번째 열까지 타일을 높는 경우의 수라 하자. 이 경우 dp[5]의 경우 아래 그림처럼 dp[4]에 2x1 타일을 놓는 경우와, dp[3]에 1x2 타일 2개를 놓는 경우가 있을 것이다. 즉, dp[x] = dp[x-1] + dp[x-2] 로 구할 수 있다. 답은 dp[n]이 된다. 그럼 다음으로 대칭인 경우를 제외해보자. 열이 홀수개일 경우 대칭인 경우는 이하처럼 중간에 2x1 타일이 있는 경우이다. 즉, dp[n]에서 dp[(n-1)/2] 를 빼주면 된다! (대칭인 경우를 빼면 되므로) 열이 짝수개인 경우엔 다음의 두 가지 경우.. 2023. 4. 3.

티스토리툴바