수학115 [코틀린, 자바] 백준 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. [자바] 백준 22938 - 백발백준하는 명사수 (boj java) 문제 : boj22938 두 점의 거리가 두 반지름의 합보다 작으면 YES, 같거나 크다면 NO를 출력해주면 된다. 두 점 사이의 거리는 이하 그림을 통해알 수 있듯이 피타고라스의 정리를 통해 얻을 수 있고, 그 값이 r1+r2 보다 더 큰지 작은지에 따라 겹치는지 확인 가능하다. 이 때 한 점에서 만나는 경우는 두 점의 거리와 r1+r2가 동일한 경우이다. 수식으로 보면 다음과 같다. 그리고 양변을 제곱해서 2번째 수식으로 풀어야 실수 오차 없이 풀 수 있다. 주의점은 X, Y, R이 모두 최대 10^9의 큰 수이므로, 제곱한 값이 int 범위를 넘어가게 되므로 long으로 연산을 해줘야 한다. 최대 (r1+r2)^2이 (2*10^9)^2 으로 대략 4*10^18인데, long은 대략 9*10^18 까.. 2022. 6. 6. [자바, 파이썬] 백준 13706 - 제곱근 (boj java) 문제 : boj13706 단순히 제곱근(루트)을 구하는 간단한 문제긴한데, 문제는 정수의 자리수가 최대 800자리나 된다는 점이다. 따라서 큰 수 연산이 필요하다. 파이썬의 경우엔 애초에 무한정 크기의 숫자 표현이 가능하다. 다만 단순히 int(input())**0.5 와 같은 코드로는 불가능한데, 너무 큰 수에대해서는 **0.5가 사용 불가하다고 한다. 찾아보니 math에 isqrt 라는 함수가 있어서 그걸 사용했다. 자바의 경우엔 우선 큰 수의 경우엔 BigInteger로 표현 가능하다. 그리고 BigInteger에 sqrt라는 함수가 있으므로 해당 함수를 사용하면 되는데, 문제는 이게 자바 9에서 추가되었다. 따라서 자바9 이상에서는 간단하다. 자바 8 이하에서 짤려면 비트 연산을 활용해서 직접 제.. 2022. 6. 1. 이전 1 ··· 6 7 8 9 10 11 12 다음
