본문 바로가기

전체 글1049

백준 20856 자바 - Tunnelbaneplatser (BOJ 20856 JAVA) 문제 : boj 20856 입력받은 a1, a2, a3, a4에 대해 확실한것부터 제거해나가면서 선택해가면 된다(그리디). 이하 설명에서 cnt는 결과값으로 출력할 변수이다. 1. a4값만큼 cnt에 더한다. (4명이니 그냥 바로 앉으면 된다. 다른 그룹과 같이 앉을 수 없다.) 2. 다음으로 a2값을 보자. a2는 a2혼자 혹은 a2+a2, a2+2*a1의 형태로 가능하다. a3와 앉을 방법이 아예 없다. 따라서 a2를 2로 나눈 몫만큼 cnt를 더하고, a2를 2로 나눈 나머지가 있다면 cnt를 하나 더 올려주면 된다. 이 때 a1이 2 이상이라면 a1 두 그룹과 같이 앉고, 아니면 a2 혼자 앉으면 된다. 근데 사실 어차피 a2랑 같이 앉을 수 있는건 a1 뿐이므로 a1이 음수가 되던말던 상관없이 .. 2021. 11. 28.
백준 1515 자바 - 수 이어 쓰기 (BOJ 1515 JAVA) 문제 : boj 1515 입력으로 주어지는 수는 최대 3000자리이고, 0~9까지는 10개이다. 그러므로 대충 생각해봐도 아무리 최악의 케이스라 할지라도 3000 * 10 = 30000 이내에서 모두 찾아질 것임을 알 수 있다. 그러므로 brute force로 입력받은 값을 첫 자리부터 확인하며 1부터 30000까지 입력으로 받은 값에 대입해보며 하나씩 찾아나가면 된다. 예를들어 290119을 보자. 첫 자리수부터 확인한다. 여기서 base라는걸 1로 두고, base를 1씩 증가시키며 쭉 매칭시키자. 우선 'base=1'은 현재 pointer가 보고있는 2와 겹치는게 없으니 다음으로 넘어간다. 'base=2'는 pointer와 동일하므로 찾은거다. pointer를 전진한다. 그리고 base가 현재 1자리.. 2021. 11. 28.
CodeForces 1614B - Divan and a New Project (Java) 문제 : https://codeforces.com/contest/1614/problem/B 어려워 보일 수 있는데, 더 많이 방문할수록 가까이 두면 된다. 예를들어 다음의 경우를 보자. 5 3 8 10 6 1 그럼 얘네들을 더 많이 방문하는 순서대로 정렬해보면 10 > 8 > 6 > 3 > 1이 된다. 그리고 시작지점을 '0'에 둔다고 해보자. 그럼 다음과 같이 배치하면 전체 거리가 최소가 된다. 즉 로직은 다음과 같다. 1. 들어온 값에 대해 내림차순으로 정렬한다. 이 때, 처음 들어왔던 순서를 알아야 정렬하더라도 처음 들어온 순서에 맞게 출력해줄 수 있다. 2. 시작점을 0으로 잡고, '1'에서 정렬한 순서대로 거리가 짧은곳에 둔다. (+1 -> -1 -> +2 -> -2 -> +3 -> ...) 시.. 2021. 11. 27.
CodeForces 1614A - Divan and a Store (Java) 문제 : https://codeforces.com/contest/1614/problem/A 처음엔 냅색문제로 예상했는데, 생각해보니 그냥 작은 값부터 그리디로 확인해봐도 만족할 것 같아 노선을 변경함! 1. 우선 전처리로, 입력으로 들어온 a 중 l 미만이거나 r 초과인 값은 버려버린다. 2. '1'에서 걸러서 남겨진 값들을 정렬한다. 3. 이제 그리디하게 작은 숫자부터 k에서 빼가면서, 0보다 작아지는 경우 그 전까지 구매할 수 있다. 코드 : github import java.io.DataInputStream; import java.io.IOException; import java.util.ArrayList; import java.util.Collections; import java.util.Comp.. 2021. 11. 27.
CodeForces 1593A - Elections (Java) 문제 : https://codeforces.com/contest/1593/problem/A 입력으로 들어온 a,b,c 중 max값을 구한다. 이 때 다음과 같이 나눠서 확인해볼 수 있다. 1. 현재 확인하는 값(a,b,c 중 하나)이 max값과 같고, max값과 동일한 후보자가 2명 이상인 경우 = 1 2. 현재 확인하는 값(a,b,c 중 하나)이 max값과 같고, max값과 동일한 후보자가 1명인 경우 = 0 3. 현재 확인하는 값이 max값보다 작은 경우 = max - 현재확인중인값 + 1 코드 : github import java.io.DataInputStream; import java.io.IOException; public class Main { private static int res(int .. 2021. 11. 27.
CodeForces 1569B - Chess Tournament (Java) 문제 : https://codeforces.com/contest/1569/problem/B 1. 타입1인 사람에 대해 다른 모든 사람들과 무승부처리를 함 (22, 23 line) 2. 동시에 타입2인 사람을 별도로 list로 관리함 (26 line) 3. 그럼 위의 과정으로 일단 타입1인 사람들은 이제 신경 쓸 필요가 없어짐. 그리고 타입2인 사람들에 대해서만 생각해보면 되는데, 타입2인 사람이 0명이면 그냥 첫번째 과정 거친거 출력하면 끝임. 타입2인 사람이 1명이거나 2명뿐인 경우 조건을 만족할수가 없음. 이 경우가 'NO'가 됨. 타입2가 3명 이상인 경우, 서로 돌아가면서 져주면 됨. 4. 내 경우엔 예를들어 A, B, C, D 라는 타입2인 사람이 있다면 일단 마지막 D가 A를 이긴걸로 침. (.. 2021. 11. 27.
CodeForces 1569A - Balanced Substring (Java) 문제 : https://codeforces.com/contest/1569/problem/A 1. 입력을 받은 값에 대해 a와 b가 나온 횟수를 prefix sum으로 계산해둔다. -> 범위 내의 a와 b의 개수를 빠르게 구하기 위해 2. 그 후 모든 substring에 대해 누적합 배열에서 범위합이 동일한 경우가 있는지 확인한다. 코드 : github import java.io.DataInputStream; import java.io.IOException; public class Main { public static void main(String[] args) throws Exception { initFI(); int tc = nextInt(); StringBuilder sb = new StringBui.. 2021. 11. 27.
CodeForces 1567A - Domino Disaster (Java) 문제 : https://codeforces.com/contest/1567/problem/A 뭔가 복잡해보이지만, 그냥 쭉 보면서 D -> U, U -> D, L과 R은 그대로 출력하면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int t = Integer.parseInt(br.readLine()); StringBuilder sb = ne.. 2021. 11. 27.
CodeForces 4A - Watermelon (Java) 문제 : https://codeforces.com/contest/4/problem/A 수박을 짝수 무게의 두 조각으로 나눌 수 있어야 한다. 짝수 + 짝수 = 짝수 이고, 짝수는 2 이상이어야 하므로 입력으로 들어온 'w'가 4 이상의 짝수인지만 확인하면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int w = Integer.parseI.. 2021. 11. 27.
백준 2697 자바 - 다음수 구하기 (BOJ 2697 JAVA) 문제 : https://www.acmicpc.net/problem/2697 A와 같은 구성에 A보다 큰 수 중 가장 작은 수는 그리디로 해결할 수 있다. 사실 이건 그리디야! 하고 푼건 아니고, 규칙을 찾고보니 그리디 스러운 규칙이었다.ㅋㅋ 1. 수를 뒤에서부터 한 자리씩 보면서, 처음으로 수가 이전보다 작아진 지점을 찾는다. 해당 지점을 T라고 하겠다. 2. T위치 이전은 그대로 출력한다. 그리고 T 위치를 포함해, 그 이후 위치에 대해 나왔던 숫자들을 몇번씩 나왔는지 카운팅한다. 3. T 이후의 위치에 있는 수 중, T에 해당하는 수보다 크면서 가장 작은 수를 찾아 T의 위치에 넣는다. 4. 카운팅해둔 값을 가지고, 작은 숫자부터 차례대로 카운팅값 횟수만큼 출력한다. 설명하기가 애매하니 예시를 들어 .. 2021. 11. 26.

티스토리툴바