수학117 [ABC259] D - Circumferences (AtCoder Beginner Contest 259 in Java) 문제 : abc259_d 내 경우엔 그래프로 변경해서 풀었다. 우선 ArrayList의 idx를 기준으로 0번에 s, 1번에 t를 둔다. 이후 N개의 원을 입력받으면서 s와 t를 포함해서 모든 원의 쌍들에 대해 서로 인접해 있다면 양방향 간선을 연결한다(코드의 edgeChk, O(3000^2)). 단, s와 t의 경우엔 외곽선에 겹칠 경우에만 겹친다고 판단하고 간선을 연결한다(코드의 circumferenceChk). 예를들어 이하의 입력을 보자. 4 0 -2 3 3 0 0 2 2 0 2 2 3 1 -3 3 3 이에 대한 이미지와 각 idx는 다음과 같다. 그리고 간선정보는 다음과 같다. (예를들어 1행 4열의 v는 idx 1과 idx 4가 인접함을 뜻한다.) 그럼 이제 이 문제는 N+2개의 정점이 있는 .. 2022. 7. 11. [ABC259] A - Growth Record (AtCoder Beginner Contest 259 in Java) 문제 : abc259_a 예를들어 N=4, T=10, D=3, X=3 인 경우를 그려보면 다음과 같다. 이 때, X부터는 변화가 없으므로 M이 X이상이라면 단순히 T가 답이 된다. 그 이하의 경우가 문제인데 그 이하의 경우엔 일정하게 줄어들게 되므로 T-(X-M)*D 가 될 것이다. 말로 설명하면 [X일때의 키(T)]-[X에서 몇 번 D만큼 내려가야하는지(X-M)]*[키의 변화수치(D)] 이다. 코드 : github ... private void solution() throws Exception { int n = nextInt(); int m = nextInt(); int x = nextInt(); int t = nextInt(); int d = nextInt(); if (m >= x) { System... 2022. 7. 11. [코틀린, 자바] 백준 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. [자바] 백준 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. [자바] 백준 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. [자바] 백준 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. [자바, C#] 백준 1225 - 이상한 곱셈 (boj java csharp) 문제 : boj1225 우선 최악의 경우는 99999....9(10000자리) 라는 수가 두개 있는 경우이다. 이 때 총 합은 9x9x10000x10000으로 81억이 되므로, 계산의 결과는 int로 표현할 수 없음을 알 수 있다. 따라서 결과 표현은 long으로 해줘야 한다. 또한 입력으로 들어온 A와 B는 10000자리까지 가능하므로 long으로도 당연히 표현이 불가하다. 어차피 각 자리의 수만 알면 되므로 String으로 입력받으면 문제 없다. 즉, A와 B를 String으로 입력받은 뒤 각 자리의 가능한 모든 조합에 대해 character를 숫자로 변환해 곱해서 결과에 더해주는 과정을 코드로 옮겨주면 된다. 예를들어 A=abc, B=de라면(e.g. A가 211 이라면 a=2, b=1, c=1) .. 2022. 6. 21. [자바] 백준 2028 - 자기복제수 (boj java) 문제 : boj2028 항상 n^2의 자리수는 n보다 크거나 같다. 따라서 n^2과 n에 대해 둘 다 낮은 자리수부터 한 자리씩 빼내고(n%10), 둘을 비교한 후 둘 다 낮은 자리수를 없앤다(n/10). 이걸 n이 0이 될 때 까지 반복하면 n에 해당하는 자리수만큼 비교할 수 있다. 예를들어 n이 11일 경우, n^2을 nPow라 하면 nPow=121이다. 처음에 n%10과 nPow%10을 비교하고 동일하므로 n/=10, nPow/=10을 해주면 1과 12가 된다. 마찬가지로 다시 n%10과 nPow%10을 비교하고 이번엔 다르므로 NO를 출력해주면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; publi.. 2022. 6. 14. [자바] 백준 23825 - SASA 모형을 만들어보자 (boj java) 문제 : boj23825 각 문자를 만드는데에 n이 2개, m이 2개 필요하다. 따라서 중요한건 둘 중 더 작은 수치이다. 만약 n이 4, m이 1000000 이라고 한다면 결국 n은 4/2개로 2개까지 가능한거니, m이 얼마나 많던지 상관이 없게 되는 것이다. 따라서 이하의 수식을 구해주면 된다. 코드 : 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 InputStreamRe.. 2022. 6. 13. [자바] 백준 10986 - 나머지 합 (boj java) --- 이해하기 어렵게 작성한 것 같아서 새로 작성했습니다. 이 글(링크)을 보시는게 더 나을 것 같습니다. --- 문제 : boj10986 i번 까지 누적합을 계산한 값이 arr[i]라고 하자(1 2022. 6. 7. 이전 1 ··· 6 7 8 9 10 11 12 다음
