문제풀이https://www.acmicpc.net/problem/1016 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다. 문제가 아주 심플하다. 그렇지만1 ≤ min ≤ 1,000,000,000,000min ≤ max ≤ min + 1,000,000범위가 악랄하다. 10^12이니 단순히 1번만 돌아도 무조건 timeout이라는 것min~max의 범위가 10^6 밖에 되지 않는다는 것을 염두에 두고 풀이를 해야 한다. 주어진 조건을 조금 변형해보자.제곱 ㄴㄴ수가 아닌 제곱 ㅇㅇ수를 구해보자.즉, X가 1보다 큰 제곱수로 나..
문제 분석https://www.acmicpc.net/problem/1013주어진 정규식에 해당하는 문자열인지 판단하는 로직을 만들면 되는 문제다. 난도 자체는 쉽겠지만 문제는 경우의 수를 정말 잘 따져야 한다.. 나는 문자를 1개씩 붙여보며 가능성이 있는 지 판단하는 방식으로 구현했다. idx를 증가시켜가며 StringBuilder에 char를 계속 append하고해당 StringBuilder의 크기를 기준으로1 -> 패턴이 될 가능성이 있음2 -> 01은 패턴이니 sb 초기화 ,10 은 패턴이 될 가능성이 있음3-> 100은 패턴이 될 가능성이 있음4up -> 0이 추가된 경우 -> 직전이 0이였다면 100000...의 형태로 패턴이 될 가능성이 있음 ..
문제 분석https://www.acmicpc.net/problem/1202무게와 가격을 가진 N개의 보석이 있고최대 C의 무게까지 담을 수 있는 가방에 최대 1개의 보석을 담을 수 있으며 이런 가방이 K개가 있을 때 담을 수 있는 최대 가치를 구하는 문제다. 맨 처음에는 냅색같이 생겼다 싶었는데, 잘 읽어보니 K개에 최대 1개만 담을 수 있다고 적혀있었다. 다음으로 떠올렸던건 세그먼트 트리인데1. N개의 보석에 대해서 무게 순으로 쭉 정렬을 하고2. 각 무게의 시작 index를 저장하는 Map을 만들고3. 정렬된 배열을 기반으로 하는 최댓값 세그먼트 트리를 만들고4. 들어오는 가방마다그리디하게 0부터 해당 가방 크기에 해당하는 구간까지의 최댓값을 구하고5. 사용된 보석의 가치를 0으로 만들고 세그먼트 ..
분석 https://www.acmicpc.net/problem/31782 N*M 배열에 O로 표시된 장소와 사방 중 2방이 인접하면 자신도 O가 되고밤에는 최악의 경우로 K명이 다시 *이 된다. 수많은 낮과 밤에도 계속해서 낮에 O가되는 사람의 수를 구하는게 문제이다. 사실 어떤 패턴이 있을까 싶어 처음에 생각을 좀 해봤지만 딱히 특정 패턴을 찾기는 힘들었다.다만, 시작하는 시점은 낮이라는 점을 고려해보면 생각보다 해결 방법은 간단했다. 예제 2번의 경우O.....O..O.....O....O.O...O.......O의 형태로 주어지는데 낮을 반영하게 되면 OOO..OOOOO..OOOOO..OOOOO..OO.....OO이렇게 된다. 여기서 1명을 어떤 식으로 .으로 바꿔도 다시 낮에 O이 된다.하지만, 여..
문제 설명은 https://www.acmicpc.net/problem/17433에서 직접 확인하자..! 처음 시도 방법n개의 수가 같은 나머지를 가지게 하는 값 M을 찾아야 한다.만약 a와 b가 다른 수 이면, 특정 수 부터는 a와 b를 나눈 나머지가 항상 다를 수 밖에 없다. 그렇기에 이러한 limit 지점을 찾고, 2부터 가능한 M 중 최댓값을 반환하면 되지 않을까 ?라는 생각으로 출발했다. 주어진 수 배열을 Set에 넣어 중복없이 만들고 다시 List에 넣고 정렬하여 사용했다.(중복된 수 끼리는 항상 나머지가 같으니깐) 정렬 후 1,2번째 원소를 기준으로 limit을 설정했다.1번째 원소를 a 2번째 원소를 b라 가정하면가능한 경우의 수는 a0aa>0, b>0 위 3가지 밖에 존재하지 않고 각 경..
import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; class Solution { public long solution(int n, int m, int x, int y, int[][] queries) { long answer = -1; Set pointList=new HashSet(); pointList.add(new Point(x,y)); for (int i = queries.length-1; i >=0; i--) { Set newPointSet=new HashSet(); int type = queries[i][0]; int dis = queries[i][1]; // System..
6,7,8 런타임 오류 코드 import java.util.*; class Solution { static boolean[] isChecked; // boolean[] isVisited; static long[] valueArr; static Map edgeMap; static long count; public long solution(int[] a, int[][] edges) { isChecked=new boolean[a.length]; // isVisited=new boolean[a.length]; // valueArr=a.clone(); valueArr=new long[a.length]; edgeMap=new HashMap(); count=0; //한 노드 잡고 그 자식 노드들 싹 돌면서 값의 합을..
import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; class Solution { public int solution(int n, int[][] edge) { int answer = 0; Queue queue=new LinkedList(); queue.add(new Node(1,0)); int[] minRoot=new int[n+1]; List[] graph=new ArrayList[n+1]; for (int i = 1; i node.cost+ newNode.cost){ minRoot[newNode.idx]=node.cost+ newNode.cost; queue.add(n..
