본문 바로가기

백준756

[코틀린, 자바] 백준 14651 - 걷다보니 신천역 삼 (Large) (boj kotlin java) 문제 : boj14651 우선 3의 배수를 판정하는 방법부터 알아보자. 이 경우 수 A의 모든 자리의 숫자의 합이 3의 배수라면 A도 3의배수이다(정수론). 그럼 이 문제는 N자리 숫자에 대해, N번의 선택을 거친 결과 모든 자리 수의 합이 3의 배수인 경우의 수를 찾는 문제인 셈이다. 물론 단순하게 brute force로 찾아보려 한다면 O(3^33333)이 필요하므로 불가능하다. DP로 생각해보자. dp[a][b]를 a번째 자리수까지 더했을 때의 합을 3으로 나눈 나머지가 b인 경우의 수로 정해보자. 그럼 a가 5일때까지만 살펴보자. (N=5) 1. 우선 a=1 일 경우 다음과 같이 될 것이다. 또 이렇게 두면 '0으로 시작하는 수는 만들 수 없는 수 이삼' 부분을 별도로 처리하지 않아도 되기 때문에.. 2022. 7. 10.
[코틀린, 자바] BOJ 15645 - 내려가기 2 (boj kotlin java) 문제 : boj15645 ps. 코틀린의 경우 대강 인터넷 검색해서 문법을 익혔으므로 아직 늅늅이 상태여서 많이 어색하게 짰다. 이 문제의 경우 dp로 풀면 쉽게 풀린다. 알아야 하는 정보는 바로 직전 3칸의 합계 뿐이다(시작할때는 당연히 셋 다 0이라고 치면 된다.). N개의 줄을 입력받으면서, 매번 해당 칸으로 올 수 있는 값 중 최대와 최소값을 갱신 후에 현재 줄에서 입력받은 값을 더해주면 된다. dp[a][b]가 a라인까지 입력받았을 때 b번째(0,1,2로 3개) 칸까지의 최대합계라고 해보자. 그렇다면 dp[x][0] = max(dp[x-1][0], dp[x-1][1]) + 입력받은 0번째 값 dp[x][1] = max(dp[x-1][0], dp[x-1][1], dp[x-1][2]) + 입력받은 .. 2022. 7. 9.
[자바] 백준 10409 - 서버 (boj java) 문제 : boj10409 n번동안 정수를 입력받으면서, 남은 t에 입력받은 정수를 뺀 값이 양수인 동안 cnt라는 값을 증가시켜준고 t를 입력받은만큼 빼준다. 그리고 n개를 모두 입력받거나, 남은 t가 음수가 된 경우 cnt를 출력해주면 된다! 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokeniz.. 2022. 7. 8.
[자바] 백준 9295 - 주사위 (boj java) 문제 : boj9295 1. 테스트 케이스 수를 입력받고, 반복문으로 테스트케이스 수만큼 반복하면서 현재 테스트 케이스 몇 번 인지 알 수 있어야 한다. 2. 두 개의 숫자를 입력받아 합을 구할 수 있어야 한다. 위 두가지를 할 수 있다면 풀 수 있다! 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = .. 2022. 7. 7.
[자바] 백준 23795 - 사장님 도박은 재미로 하셔야 합니다 (boj java) 문제 : boj23795 1. -1이 뜰 때 까지 계속 한줄씩 입력받아 int로 변경하는 로직 2. '1'의 int값을 계속해서 더하다가 -1이 뜨면 출력하고 종료하는 로직 위의 두가지만 잘 구현해주면 된다. 코드 : 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 sum = 0; while (true) { int cur = Integer.parseInt(br.readLine(.. 2022. 7. 6.
[자바] 백준 2153 - 소수 단어 (boj 2153) 문제 : boj2153 1. 문자를 문제에서 제시된 방법대로 합계를 구할 수 있어야 한다. -> 문자의 각 character인 c를 확인하면서 아래처럼 구하자. - 'a'~'z'인 경우 : sum += 1+c-'a'; - 'A'~'Z'인 경우 : sum += 27+c-'A'; 2. '1'에서 구한 sum이 소수인지 소수판정을 해야 한다. -> 이 경우 2부터 sqrt(sum) 까지의 정수로 직접 나눠보고, 이 중 하나라도 sum을 나누어떨어지게(나머지가 0) 하는 값이 있다면 소수가 아니다. sqrt(sum) 까지 확인하는 이유는 '에라토스테네스의 체 혹은 소수판정 시 제곱근 까지만 확인하면 되는 이유' 글에 적어두었다(링크). 코드 : github import java.io.BufferedReader;.. 2022. 7. 5.
[자바] 백준 2470 - 두 용액 (boj java) 문제 : boj2470 예시 입력 1을 봐보자. 5 -2 4 -99 -1 98 위 상태로만 보자면, 결국 O(N^2)으로 모든 쌍을 확인하는 것 외에 별다른 방법이 떠오르지 않을 것이다. 정렬을 하면 어떨까? -99 -2 -1 4 98 이 경우 가장 좌측에서 시작하는 포인터를 s, 가장 우측을 e라고 해보자. 's의 값 + e의 값'을 기준으로 포인터를 중앙으로 점차 가져와보자. - 두 포인터가 가르키는 값의 합이 0 초과이라면 -> 더 작은 값을 확인해야하니 e를 좌측으로 이동한다. - 두 포인터가 가르키는 값의 합이 0 미만이라면 -> 더 큰 값을 확인해야하니 s를 우측으로 이동한다. 위 두가지 경우에 따라 s와 e를 중앙으로 이동시키면서 0과 가장 가까운 값을 찾으면 된다! 위의 경우 1. s=-9.. 2022. 7. 4.
[자바] 백준 23802 - 골뱅이 찍기 - 뒤집힌 ㄱ (boj java) 문제 : boj23802 규칙을 잘 찾아 그대로 구현해보자. 규칙은 아래와 같다. 1. N개의 줄에 5N개 만큼의 '@'을 출력한다. 2. 4*N개의 줄에 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.readLine()); StringBuilder sb = new StringBuilder(); f.. 2022. 7. 3.
[자바] 백준 20001 - 고무오리 디버깅 (boj java) 문제 : boj20001 남은 문제에 해당하는 cnt를 둔다. 이 경우 1. '문제'가 입력으로 들어왔을 때 cnt를 1 줄인다. cnt가 -1이라면 cnt를 2로 변경한다. 2. '고무오리'가 입력으로 들어왔을 때 cnt를 1 늘린다. 최종적으로 '고무오리 디버깅 끝'이 들어왔을 때 cnt가 0이라면 '고무오리야 사랑해', 아니라면 '힝구'를 출력해주면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private void solution() throws Exception { BufferedReader br = new BufferedReader(new InputStream.. 2022. 7. 1.
[자바] 백준 1835 - 카드 (boj java) 문제 : boj1835 이걸 어찌 구해야할지 상당히 난감해보일 수 있다. 그럼 반대로 이미 출력의 답을 알고 있다고 할 때, 이 문제에서 제시된 방법대로 진행할 경우 정말 1,2,3,... 이 순서대로 뜰지 확인해볼 수 있을까? 물론 문제에서 제시된대로 코드를 구현만 하면 확인해볼 수 있다. 그렇다면, 이미 답을 알고있다고 가정하고 시뮬레이션을 돌려보자. 그리고 뽑히는 순서대로 1,2,3... 을 넣어준 후, 답의 출력순서대로 다시 짜맞춰주면 된다. 무슨 말이냐면, 아래 그림을 봐보자. 그리고 자바에서 클래스는 주소값을 기준으로 저 링크를 연결해두기 좋다. 그러니 ?로 된 카드들을 배열에 넣어두고, 해당 값들을 덱에다가 미리 넣어둔다(위 그림의 '1'에서 위쪽 파란거 3개가 배열, 아래쪽이 덱에 들어간걸.. 2022. 6. 30.

티스토리툴바