본문 바로가기

백준756

[자바] 백준 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.
[자바] 백준 5789 - 한다 안한다 (boj java) 문제 : boj5789 짝수개수의 문자가 들어오므로, 입력이 어떻게 들어오던지 상관없이 중앙의 두 문자만 확인하면 된다. 입력으로 들어온 문자열의 길이를 기준으로 중앙의 두 글자를 비교해서 답을 출력해주면 된다. 코드 : 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 S.. 2022. 6. 12.
[자바] 백준 2154 - 수 이어 쓰기 3 (boj java) 문제 : boj2154 n이 최대 100000이므로, 모두 이어쓴다고 해도 500000개 이하 정도 수준의 character 수로 구성될 것이다. 따라서 직접 해당 문자열을 만들어주고, 문자열에서 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()); StringBuild.. 2022. 6. 11.
[자바] 백준 8462 - 배열의 힘 (boj java) 문제 : boj8462 가장 간단한 방법으로, 각 쿼리마다 직접 해당 범위를 순회하면서 가장 많은 등장 수를 찾는 것은 당연히 간단하다. 하지만 그러면 O(TN)이 될 것이므로 시간초과가 나게 된다. 그러니 이번엔 이전 쿼리의 결과를 이용할 방법을 생각해보자. 첫 번째 쿼리가 i=3, j=10이고 두 번째 쿼리가 i=5, j=11 이라고 해보자. 그림으로 나타내면 아래와 같다. 이 경우 만약 위에서 말한 방법대로 매번 직접 순회하며 볼 경우 첫 번째 쿼리는 8번, 두 번재 쿼리는 7번을 봐야하므로 총 15번을 봐야한다. 하지만 첫 번째 쿼리에서 i가 +2가 됬으므로 주황색으로 빗금친 부분을 빼면 2번을 빼면 되고, 마찬가지 방식으로 파란 빗금부븐을 1번 더해줄 수 있다. 그럼 총 15번 필요했던게 3번으.. 2022. 6. 10.
[자바] 백준 13548 - 수열과 쿼리 6 (boj java) 문제 : boj13548 우선 가장 간단한 방법으로, 각 쿼리마다 직접 해당 범위를 순회하면서 가장 많은 등장 수를 찾는 것은 당연히 간단하다. 하지만 그러면 O(MN)이 될 것이므로 시간초과가 나게 된다. 그러니 이번엔 이전 쿼리의 결과를 이용할 방법을 생각해보자. 첫 번째 쿼리가 i=3, j=10이고 두 번째 쿼리가 i=5, j=11 이라고 해보자. 그림으로 나타내면 아래와 같다. 이 경우 만약 위에서 말한 방법대로 매번 직접 순회하며 볼 경우 첫 번째 쿼리는 8번, 두 번재 쿼리는 7번을 봐야하므로 총 15번을 봐야한다. 하지만 첫 번째 쿼리에서 i가 +2가 됬으므로 주황색으로 빗금친 부분을 빼면 2번을 빼면 되고, 마찬가지 방식으로 파란 빗금부븐을 1번 더해줄 수 있다. 그럼 총 15번 필요했던게.. 2022. 6. 9.
솔브닥 새싹8단계 뱃지 획득! (256일 연속) 솔브닥 새싹 8단계 뱃지를 획득했다! (256일 연속 문제 해결) 솔브닥이 생긴지 325일정도 되었으므로, 9단계(512일 연속 문제 해결)은 아직 얻은 사람이 없다. 새싹 8단계 이쁜 뱃지에 덤으로 6월6일에 시즌1 끝나면서 멋진 배경도 얻었다. 만-족 9단계까지 ㄱㅈㅇ 2022. 6. 9.
[자바] 백준 24513 - 좀비 바이러스 (boj java) 문제 : boj24513 문제를 풀 개념만 확실히 잡는다면, 그 이후로는 구현력에 달려 있는 문제이다. 구현이 상당히 복잡할 수 있다. 구현자체는 코드를 참고해서 짜보고, 일단 개념만 풀이로 작성해보겠다. 이하의 예시를 생각해보자. 3 3 1 0 0 0 0 0 0 0 2 우선 1번 바이러스가 전체 맵을 진행할 때, 각 마을에 도착하는 시간을 재보면 다음과 같을 것이다. 그 다음 2번 바이러스가 차례차례 1번 바이러스의 지점들을 덮으면서 진행해보자. 위에서 동일한 거리끼리 만나게 되었다. 즉, 해당 지점에 각 바이러스는 동일한 시각에 도착한다는 의미이다. 따라서 이 지점에서 3번 바이러스가 만들어지게 되는 것이다. 최종적으로 각 마을마다 감염되는 바이러스의 번호는 다음과 같다. -------------- .. 2022. 6. 8.
[자바] 백준 24508 - 나도리팡 (boj java) 문제 : boj24508 그리디로 생각해보자. 결국 최소 횟수로 이동하면서 K개씩을 만들려면 더 빠르게 없어질 수치가 큰 값에다, 더 느리게 없어질 수치가 작은 값을 밀어넣어야 한다. 따라서 입력으로 들어온 N개의 입력값 Ai 들을 정렬해보자. 그리고 작은 값을 큰 값에 직접 밀어넣으면서 K개를 만들면 없애는 식으로 시뮬레이션을 진행하면 풀 수 있다. 약간의 그리디가 들어간 시뮬레이션 문제로 구현력(?)이 좋다면 어렵지 않게 풀 수 있다. 이하의 코드를 참고해보자. 다만 주의해야 할 예시 2가지를 들어보겠다. [1] 3 2 10000 0 0 0 [2] 5 2 10000 1 0 0 [1] 처럼 모두 0인 경우엔 이미 조건을 만족하므로 별다른 처리없이 YES를 출력해줘야 한다. [2] 처럼 하나만 0이 아닌.. 2022. 6. 8.
[자바] 백준 14725 - 개미굴 (boj java) 문제 : boj14725 알고리즘 분류를 봤다면 트라이를 봤을텐데, 필요없다. 그냥 그래프를 활용할 줄 안다면 풀 수 있다. 결국 다음의 예제 입력 1을 3 2 B A 4 A B C D 2 A C 이하의 그래프 처럼만 표현할 줄 알면 된다. 각 정점은 먹이 이름과 간선으로 이루어진다. 그리고 동일한 depth에 동일한 이름이 존재할 경우엔 먹이 이름을 정점을 추가하지 않는다. 이것만 해주면 된다. 차후 출력 시 간선을 순서대로 순회해주며 출력하는 부분은 이하 코드처럼 매번 정렬을 해줘도 된다. 어차피 N이 최대 1000이므로, 딱히 해싱을 하지 않고 매번 모든 간선에 열결된 정점이름을 확인해도 문제 없다. 딱히 알고리즘 기법이 들어간게 없고, 그냥 그래프 자료구조 응용 문제로 상당히 좋은 문제인 것 같다.. 2022. 6. 8.

티스토리툴바