본문 바로가기

백준756

[자바] 백준 12873 - 기념품 (boj java) 문제 : boj12873 리스트를 하나 두고 미리 1부터 N까지를 순서대로 넣어놔보자. 그럼 이제 단계를 A라고 할 때, 1단계부터 N-1단계까지 A^3번을 리스트 순회하다가 해당 횟수에서 제외시키는 식으로만 진행하면 된다! 다만 이 경우 O(N*N^3) = O(N^4) 이라서 시간초과를 피하기 힘들 것이다. 약간만 생각해보면, 예를들어서 현재 6명이 리스트에 남아있고 4001단계이다. 그럼 4001 실제로 6명을 가지고 약640억번 돌아볼게 아니고, 어차피 한바퀴 돌면 제자리일테니 640억을 6으로 나눈만큼만 돌면 된다! 4001^3 % 6 = 5이다. 이런식으로 A단계에 대해 'A^3 % [현재남은수]'를 계산해서 그만큼만 움직이면 된다. 그럼 총 O(N^2)으로 줄어든다. 추가로 int가 연산이 더.. 2022. 6. 30.
[자바] 백준 11101 - 꿍의 여친 만들기 (boj java) 문제 : boj11101 문자열 파싱문제이다. 로직을 다음과 같이 나눠보자. 설명은 이하의 예제 입력 1의 테스트케이스 2를 기준으로 하겠다. 1 ab:13,b:17,cab:21 ab&b|b&cab 1. 각 테스트케이스의 첫줄을 받아 문자열을 key, 시간을 value로 하는 Map 형태로 만든다. -> ':'와 ','을 기준으로 StringTokenizer로 문자열을 나누게 되면 ab, 13, b, 17, cab, 21이 순서대로 들어가 있게될 것이다. 따라서 순서대로 {ab:13, b:17, cab:21}의 Map 형태로 만들어줄 수 있다. 이후 맵에서 쉽게 "ab"의 시간을 알 수 있다. 2. 각 테스트케이스의 둘째줄을 받아 '|' 을 기준으로 나눈다. -> 'ab&b'와 'b&cab'로 나뉠 것이.. 2022. 6. 30.
[자바] 백준 17826 - 나의 학점은? (boj java) 문제 : boj17826 이미 내림차순으로 정렬된 점수 데이터가 들어온다. arr[i]가 i번째 입력값이라고 해보자. 우선 50개의 데이터를 입력받은 후 (arr[1]~arr[50]) 홍익이의 점수 n을 입력받는다. 그리고 i라는 값을 1부터 50까지 증가시키면서 arr[i]가 n보다 작거나 같은 값이 나올 때 멈춘다. 그 때의 i가 홍익이의 등수가 된다. 이후 i를 기준으로 문제에서 제시된대로 A+, A0, ... 을 조건문을 통해 출력해주면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void.. 2022. 6. 29.
[자바] 백준 23806 - 골뱅이 찍기 - ㅁ (boj java) 문제 : boj23806 규칙을 잘 찾아 그대로 구현해보자. 규칙은 아래와 같다. 1. N개의 줄에 5N개 만큼의 '@'을 출력한다. 2. 3*N개의 줄에 N개의 '@', 3N개의 ' '(공백), N개의 '@'을 차례대로 출력한다. 3. N개의 줄에 5N개 만큼의 '@'을 출력한다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(.. 2022. 6. 29.
[자바] 백준 23794 - 골뱅이 찍기 - 정사각형 (boj java) 문제 : boj23794 규칙을 잘 찾아보자. 우선 첫 번째 줄과 마지막줄에는 N+2개의 '@'를 출력한다. 그 사이 N개의 줄은 각각 시작과 끝이 '@' 이고, 그 사이에 공백 N개가 출력된다. 위의 규칙을 코드로 구현해주면 된다. 이하 N=10인 경우! 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine());.. 2022. 6. 27.
[자바] 백준 23803 - 골뱅이 찍기 - ㄴ (boj java) 문제 : boj23803 입력과 출력을 보고 규칙을 잘 찾은 후 구현해내면 된다. 규칙찾기는 아래와 같다. 1. 4*N개의 줄을 각각 N개의 골뱅이를 가로로 채운다. 2. N개의 줄에 각각 5*N개의 골뱅이를 가로로 채운다. 위의 규칙을 그대로 코드로 구현해내면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readL.. 2022. 6. 26.
[자바] 백준 23817 - 포항항 (boj java) 문제 : boj23817 상당히 좋은 아이디어 문제라 생각한다. 얼핏 브루트포스 문제로 생각하기 힘들고, 당연히 bfs로 어떻게든 잘 해야 할 것 같이 생겼다. 하지만 잘 생각해보면 단순 탐색으로는 최소시간을 찾기 힘들고 모든 경우의 수를 보는 brute force(완전탐색)로 봐야할 것임을 알 수 있다. 로직을 나눠서 생각해보자. 1. 최대 20개의 식당에 대해 5개의 식당을 방문하는데 필요한 최소한의 시간을 구할 수 있어야 한다. 이걸 확인하려면 기본적으로 방문 순서도 중요하다. 즉 20C5가 아니라 20P5로 봐야 한다. -> 모든 정점 사이의 거리를 안다면 1000x1000 짜리 배열이 아니라 최대 21개(S가 1개, K개 20개)의 정점과 그 사이에 거리에 관한 간선이 있는 그래프로 변경할 수 .. 2022. 6. 25.
[자바] 백준 24723 - 녹색거탑 (boj java) 문제 : boj24723 뭐 복잡하게 생각할 것 없이, 1층에서 내려올 수 있는 방향은 2군데이다. 2층이라면 1층에서 2군데로 내려온 후, 1층에서 내려온 각각도 마찬가지로 2군데로 내려올 수 있다. 3층이라면 2층에서 내려온 녀석들이 각각 2군데로 내려갈 수 있다. 즉, 2^N 을 출력해주면 되는 문제이다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = I.. 2022. 6. 25.
[자바, 파이썬] 백준 14928 - 큰 수 (BIG) (boj java python) 문제 : boj14928 문제 자체는 아주 심플하다. 문제 그대로 N을 20000303으로 나눈 나머지를 출력해주면 된다. 문제는 큰 수를 지원해주는 언어에 따라 난이도가 매우 다르다는 점이다. 파이썬의 경우 큰 수를 지원하므로 그냥 n을 입력받아 나머지를 출력만 해주면 끝난다(물론 오래걸린다). 자바의 경우엔 BigInteger로 큰 수를 지원해주긴한데, 시간초과로 통과가 안된다ㅋㅋㅋ 사실상 파이썬으론 엄청 쉽고, 나머지 언어론 큰 수를 지원해줘도 시간초과가 날 것 같다. 아무튼 그럼 파이썬은 풀이라고 할게 없으니 자바코드를 풀이로 작성해보겠다. 이걸 파이썬처럼 단순히 푸는게 아니라 직접 풀려면 결국 나머지 연산(%)에 대한 수학적 지식이 좀 필요하다. 나머지 연산에도 분배법칙이 있는데 덧셈에 대해 다.. 2022. 6. 25.
[자바] 백준 6755 - Who is taller? (boj java) 문제 : boj6755 입력으로 들어온 M개의 x가 y보다 크다는 정보를 가지고, p가 q보다 큰지(yes) 혹은 q가 p보다 큰지(no) 혹은 검증이 불가한지(unknown) 알아낼 수 있어야 한다. 그래프로 생각해보자. 우선 각 N명의 사람을 정점으로 하고, 간선을 x에서 y로 (즉 큰 사람에서 작은사람쪽으로) 하는 방향 그래프를 생각해보자. 그럼 간단히 p에서 q로 간선을 타고 이동이 가능하다면 p가 q보다 큰게 된다. 반대로 q에서 p로 간선을 타고 이동이 가능하다면 q가 p보다 큰게 된다. 둘 다 불가했다면 검증이 불가하다. 지문의 'you always compare correctly'에 따라 사이클이 생긴다거나, p에서 q로도 갈 수 있고 q에서 p로도 갈 수 있는 상황은 그냥 문제가 틀린셈이.. 2022. 6. 25.

티스토리툴바