https://www.acmicpc.net/problem/11659문제풀이처음엔 배열을 stream()을 사용하여 구간 합을 구하면 될 것 같았는데 시간초과가 났다누적합을 배열에 저장해두는 방식으로 진행하였다원본 배열 arr이 있다누적합을 저장할 배열 sum을 만든다. sum[i]는 0부터 arr[i]까지의 합이다sum[0] = 0 으로 초기화하고 'sum[i] = sum[i - 1] + arr[i]'로 sum 배열을 완성한다인덱스 x부터 y까지의 합을 구하고 싶다면 sum[y] - sum[x - 1]을 계산하면 된다sum[y] = arr[0] + arr[1] + ... + arr[x - 1] + arr[x] + ... + arr[y]sum[x] = arr[0] + ... + arr[x]sum[y] - ..

https://www.acmicpc.net/problem/9461문제풀이규칙을 찾기 위해 1~10까지 파도반 수열을 구해보았다P(1) = P(2) = P(3) = 1P(4) = P(1) + P(3)P(5) = P(4)P(6) = P(1) + P(5)P(7) = P(2) + P(6)P(8) = P(3) + P(7)P(9) = P(4) + P(8)P(10) = P(5) + P(9)P(5)까지는 규칙이 없어보이지만 P(6)부터는 규칙이 보인다P(N) = P(N - 5) + P(N - 1) 수식 그대로 다이내믹 프로그래밍을 하여 Top-Down 방식으로 구현하였다코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;..

http://acmicpc.net/problem/2606문제풀이dfs로 구현 가능한 문제이다연결되어 있는 컴퓨터를 표시하기 위해 com[][] 배열을 만들고 입력값에 맞게 com[x][y], com[y][x]를 1로 초기화한다dfs를 돌면서 방문한 노드는 true로 해주고 감염된 컴퓨터 수를 +1 해준다연결된 컴퓨터만 체크하고 방문하지 않은 노드일 때만 dfs 함수를 적용한다코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Main { static int[][] com; static boolean[] visited; static int cnt = 0; stati..

https://www.acmicpc.net/problem/2579문제풀이계단을 오를 때 합을 계속 기억하고 있어야 하기 때문에 다이내믹 프로그래밍으로 풀어야 한다Top-Down 재귀 형식으로 해결하려 하는데 핵심은 N-1 일 때는 재귀 호출을 하지 않는다는 점이다왜냐하면 연속된 세 개의 계단은 밟을 수 없기 때문에 N-2의 dp값과 N-3 dp값에 arr[N-1]을 더한 값 중 큰 것을 선택하고 자기 자신의 값을 더한 것을 dp[N]으로 한다코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Main { static Integer[] dp; static int[] arr; ..

https://www.acmicpc.net/problem/1003문제풀이처음에는 그냥 단순히 피보나치를 재귀로 호출하면서 0이나 1이 나올 때 카운트를 증가하였다당연하게도 시간초과가 났다 도저히 풀이 방법이 안떠올라서 Stranger's LAB 님의 풀이 방식을 참고하였다이미 구한 겂을 재사용하기 위해 DP를 활용한다한 번 탐색할 때마다 N의 0과 1의 값을 저장해두고 이후 다음 탐색에서 이미 탐색했던 노드라면 해당 값을 사용한다 dp라는 2차원 배열을 생성하고 탐색하지 않은 N에 대한 0, 1 값을 dp에 저장하면서 재귀 호출을 해준다코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public clas..

https://www.acmicpc.net/problem/17219문제풀이중복이 없기 때문에 Map을 사용해서 빠르게 탐색할 수 있게 한다시간을 줄이기 위해 BufferedReader를 사용하여 입력받는다입력 받은 주소를 get()에 바로 넣어 StringBuilder로 출력한다코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in..

https://www.acmicpc.net/problem/11399문제풀이주어진 시간을 오름차순으로 정렬한 뒤 0번째 인덱스부터 i번째 인덱스까지 총합을 계속 더해준다코드import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.*;public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; StringBuilder sb = new St..