계단을 오르듯이

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 package algo; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; public class B_2108_통계학 { public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringB..

일정한 규칙이 존재한다. 우선 문제와 같이 2차원 배열을 이용해 순차적으로 값을 더해준다. 예를 들어 주어진 값이 아래와 같다면 1 2 3 4 5 6 7 8 9 순차적으로 더한 배열의 값은 아래와 같을 것이다. 1 3 6 5 12 24 12 27 45 위의 계산을 편하게 하기 위해 나는 여분의 배열 0행과 0열을 주었다. 즉, 0 0 0 0 0 1 3 6 0 5 12 24 0 12 27 45 와 같은 결과 행렬이 될 것이다. 해당 배열[x][y] 위치의 값은 [x][y] = [x][y] + [x-1][y] + [x][y-1] - [x-1][y-1] 이다. 해당 배열 위치의 자신의 값에 위와 왼쪽 값을 더하고 이중 중복되는 왼쪽 위방향의 대각선 방향의 배열 값[x-1][y-1]을 빼준다. 이제 해당 범위 ..

피보나치에서 다이나믹 프로그래밍으로 발전된 문제이다. arr[n][2]의 저장소와 방문처리 boolean형 1차원 배열을 이용해 풀이했다. arr[n][0]= n일 경우 0의 개수, arr[n][1]= n일 경우 1의 개수이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 package algo; import java.io.BufferedReader; import java.io.InputStreamReader; public class B_1003_피보나치함수 { static int[][] f = new int[..

비교적 정답률이 낮아 풀고 싶었다. 오.. 역시 낮은 이유는 생각할 조건이 의외로 많았다. 반례를 찾아보고 왜 틀린지를 알았다. 아래에 3개의 반례와 주석을 통해 악마의 테케를 피해갈 수 있는 방법을 적어놓았다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 package algo; import java.io.BufferedReader; import java.io.InputStreamReader;..

처음 입력받는 값은 각 노드의 연결 여부를 나타내는 배열을 입력받는다. 출력해야하는 결과값은 각 노드의 연결 여부를 최대한 이용하여 서로의 노드를 연결할 수 있는지 여부를 나타내는 결과값을 의미한다. 모든 노드의 연결 상태를 모두 확인하여 최소한의 연결 경로의 값을 찾는 플로이드 워샬 알고리즘을 이용하였다. 해당 알고리즘을 이용해 모든 연결 상태의 경우를 이용해 해당 노드들이 연결 상태인지를 알아내었다. 단지 최소의 값을 찾는 플로이드 워샬 알고리즘을 연결여부만을 나타내는 것으로 약간 바꾸어 연산을 하게 하였다. 최소의 값을 찾는 것이 아닌 0이면 연결이 되지 않은 상태이고, 1이면 연결 상태임을 나타내고, k를 경로로 하여 i-k와 k-j가 연결 상태이면 i-j를 연결상태로 나타내는 방식으로 연산을 진..

백준에 비슷한 문제가 있다. 이 문제를 푼 경험을 통해 조금더 쉽게 할 수 있었다. 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 처음 가장 고민한 부분은 안쪽 치즈를 녹이지 않고 밖에 존재하는 외부 치즈만 녹이는 법을 어떻게 해야하는지 고민을 했었다. 우리는 항상 빈곳이 아닌 곳을 방문처리하고, bfs를 하였는데 이 경우는 반대로 치즈가 존재하지 않은 곳을 시작으로 계속해서 0인 곳을 큐로 넣고 연산을 시작하면, 놀랍게도 안쪽의 치즈는 영향을 받지 않게 된다. 계속해서 0인 곳만을 큐에 넣기 때문에 밖에서 외부의 치즈 방어막..

0 의 숫자가 입력으로 들어오면 가장 마지막에 받은 수를 지워야하므로 스택의 자료구조를 이용하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 package algo; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Stack; public class B_10773_제로 { public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int N = I..

문자열을 받아 각 문자의 방문처리 체크로 문제를 해결하였다. 주석과 코드로 설명을 대체하겠다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 package algo; import java.io.BufferedReader; import java.io.InputStreamReader; public class B_1316_그룹단어체커 { public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int..