본문 바로가기

PS831

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.
백준 1622 자바 - 공통 순열 (BOJ 1622 JAVA) 문제 : https://www.acmicpc.net/problem/1622 중요한건 2개의 문자열에서 각각의 문자열에 포함된 알파벳의 갯수이다. 예를들어 다음을 보자. S1 : accaab S2 : cccabbb S1은 a:3, b:1, c:2 S2는 a:1, b:3, c:3 이다. 이렇게 카운팅만 할 수 있다면, 사전순으로 가장 빠르면서 문제에서 제시된 출력은 a,b,c,d,...,z 까지 세어둔 수를 확인하면서 둘 중 작은 개수만큼 출력하면 된다. 위를 예로들면 a : 3과 1중 작은거, b : 1과 3중 작은거, c : 2와 3중 작은거. 따라서 a를 1번, b를 1번, c를 2번 출력하면 되므로 답은 abcc가 된다. 코드 : https://github.com/NaHwaSa/BOJ_BaekjunO.. 2021. 11. 25.
백준 11969 자바 - Breed Counting (BOJ 11969 JAVA) 문제 : https://www.acmicpc.net/problem/11969 breed 1,2,3에 각각 범위 내에 포함된 카운팅값의 합을 출력하면 된다. prefix sum을 활용하면 풀 수 있다. breed1,2,3로 나누어서 카운팅한 값의 누적합을 저장하는 방식으로 진행하면 된다. 예제 입력1에 대해 그려보면 다음과 같다. N번 소에 대해 breed1,2,3를 사용했음을 기입한 것이다. 이걸 breed 1,2,3에 대해 각각 누적합을 구해보면 다음과 같다. 이렇게 전처리로 누적합을 구해두고, 각 쿼리의 a, b값에 대해 범위내의 합계를 출력해주면 된다. 예를들어 a=2, b=4라면 breed1의 경우 breed1[b] - breed1[a-1] = 2 - 0 = 2, breed2의 경우 마찬가지로 1.. 2021. 11. 24.
백준 15725 자바 - 다항함수의 미분 (BOJ 15725 JAVA) 문제 : https://www.acmicpc.net/problem/15725 문자열 파싱 문제이다. 다음의 경우에 대해서 case work를 진행하면 쉽게 풀 수 있다. 1. x+n, n+x와 같은 형태(n은 아예 없이 "x"와 같은 경우도 포함) -> 1 출력 2. -x+n, n-x와 같은 형태 -> -1 출력 3. x없이 n과 같은 형태 -> 1차항이 아예 없으므로 0 (아마 여기서 많이들 틀릴 듯) 4. ax+n, n+ax의 형태 -> a 5. -ax+n, n-ax의 형태 -> -a 적절히 위의 모든 경우를 찾아내면 된다. 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/15700/BOJ_15725.java import java.. 2021. 11. 24.
백준 4781 자바 - 사탕 가게 (BOJ 4781 JAVA) 문제 : https://www.acmicpc.net/problem/4781 유명한 DP 활용 문제 유형인 냅색(knapsack) 문제이다. '각 사탕의 개수는 매우 많기 때문에, 원하는 만큼 사탕을 구매할 수 있다.'라는 부분 때문에 냅색에서 난이도가 좀 낮춰지지만, 가격이 실수라서 난이도가 다시 높아진다 ㅋㅋㅋ 결국 실수만 잘 처리할 수 있으면 DP를 사용해 풀 수 있다. 그래도 양심이 있는지 소수점 두번째 자리까지만 주어지고, 최대 100.00 이라서 그냥 100을 곱해서 처리하면 된다. 소수점을 처리할 방법들중 몇가지는 다음과 같다. 1. 주어진 실수에 100을 곱한다. -> 주의점은 입력받은 실수에 100을 곱한 후 +0.1 정도를 해줘서 소수점 오차를 없앤 후 int형으로 형변환 해야한다. 안전.. 2021. 11. 23.
백준 8598 자바 - Zając (BOJ 8598 JAVA) 문제 : https://www.acmicpc.net/problem/8598 일단은 무지성으로 BFS 돌리면 되는 문제긴 하다. 그래서 딱히 안적을까 했는데, 언어가 이상하다보니 번역기 돌려도 놓칠만한 부분 적어봄. 'x'는 못감. 'z'가 시작점. 'n'이 도착지점. 다만 문제 특성상 n에서 출발해서 z에 도착해도 상관은 없다. 그리고 제일 중요한 부분은 길이 존재하지 않을 경우 "NIE"를 출력해야 한다. 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/08500/BOJ_8598.java import java.io.DataInputStream; import java.io.IOException; import java.sql.Array.. 2021. 11. 23.

티스토리툴바