JumpUp

높이 V미터 나무막대를 낮에 A미터 올라가고 밤에 B미터 미끄러지는 달팽이가 몇일만에 나무막대를 모두 올라가는지 구하는 문제이다. 문제풀이 방법 1. 시간제한이 있는 문제이기에 Scanner가 아닌 Buffereader로 입력을 받는다. Scanner를 쓰면 기본 0.1초가 넘는다. 2. 모두 올라가고 난 후에는 미끄러지지 않는다는 조건을 확인하고 규칙을 세운다. 예) A=2, B=1, V=5 1일 낮 : A(2) = 2 1일 밤 : A(2)-B(1) = 1 2일 낮 : A(2)-B(1)+A(2) = 3 2일 밤 : A(2)-B(1)+A(2)-B(1) = 2 3일 낮 : A(2)-B(1)+A(2)-B(1)+A(2) = 4 3일 밤 : A(2)-B(1)+A(2)-B(1)+A(2)-B(1) = 3 4일 낮 ..

해당 배열에 대한 규칙을 찾아야 한다. 대각선으로 봤을 때, 최대값이 1 -> 3 -> 6 -> 10 -> 15 ..이다. 이는,1*2/2 -> 2*3/2 -> 3*4/2 -> 4*5/2 -> 5*6/2이고, 대각선 별로 n*(n+1)/2가 최대값이란 규칙을 발견된다. 그러면, 입력값이 대각선 몇번째에 포함되어있는지 범위를 찾는것이 첫번째이다. int n = sc.nextInt(); int col = 1; int max = 1; while(n>max){ col++; max = col*(col+1)/2; } // n= 14이면, col = 5, max = 15이다. 대각선 짝수번째냐, 홀수번째냐에 따라 최대값보다 작은지 큰지 달라진다. //대각선 짝수번째라면, 최대값에서 입력값 차이 만큼, //행은 작아지..

백준 단계별로 풀어보기 [문자열] 복습하면서, 유용했던 메서드/ 풀이유형 등을 정리하고자 한다. 1. StringBuilder().reverse() < 문자열 거꾸로 하기 string s = new StringBuilder().append(123).reverse().toString(); 2. 문자열 공백제거 공백제거 strip(), stripLeading(), stripTrailing() // java11이상 지원 trim() 유의사항) string s = ""; String[] S = s.strip().split(” “); //빈문자열에 공백이 없기 때문에 s.strip() = ""이며, S[0] = ""이다. 3. int형 각 자릿수 구하기 StringBuilder sb = new StringBuil..

해당 문제는 위상정렬로 푸는 문제입니다. 위상정렬은 그래프 정렬할 때 사용하는 알고리즘으로 그래프가 DAG(Directed Acyclic Graph, 방향성은 있지만 사이클은 없는 그래프)이여야 합니다. 풀이과정 필요한 자료구조는 다음과 같습니다. ArrayList[] 그래프 관계를 표현하는 인접리스트 int[] indegree 노드로 들어오는 간선 갯수를 담는 배열 Queue queue indegree가 0인 된 노드를 담는 큐 StringBuilder result 큐에서 꺼낸 노드를 출력하기 위한 StringBuilder STEP1. list인접리스트에 순서를 저장하고, 노드를 가르키는 간선 수를 indegree배열에 저장합니다. STEP2. queue에 indegree가 0인 노드를 담습니다. ST..

해당 문제에서는 다익스트라 알고리즘이 활용됩니다. 다익스트라는 하나의 노드에서 다른 모든 노드로 가는 최단 경로를 탐색하는 알고리즘입니다. 양의 가중치만 존재할 때 이 알고리즘을 사용할 수 있습니다.(이 점이 DFS, BFS을 활용한 최단경로 구하기와 다른 점 입니다.) 음의 가중치가 하나라도 있으며 다익스트라를 사용할 수 없다는 특징이 있습니다. 풀이과정 필요한 자료구조는 크게 4가지입니다. 통행정보 저장할 가중치 인접리스트 ArrayList[] arr, 도시 방문여부 확인할 visited배열, 최소비용갱신할 dis배열, 현재노드와 연결된 간선정보를 저장할 우선순위큐 1. 노드와 가중치를 담은 Bus 클래스를 선언합니다. 가중치를 기준으로 정렬할 수 있도록 compareTo를 Override해줍니다. ..

처음엔 중첩 반복문을 사용해서 풀었지만 투포인터로 푸는 것이 해당 문제의 의도였기에 투포인터를 사용해 다시 풀어보았다. 소스코드 (1) 중첩 반복문을 사용해 구현해보기 public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int S = Integer.parseInt(st.nextToken()); st = new StringTokenizer(br.re..