백준
백준 13398 : 연속합 2
문제 링크 접근 방법 DP(다이나믹 프로그래밍)로 풀이하였다. 수를 제거하지 않았을 때 최대 누적합은 sum[]에, 수를 하나 제거했을 때 최대 누적합을 sumR[]에 저장하고 누적합들 중 최대를 출력하면 된다. sum[i] = Math.max(0, sum[i-1]) + num[i]; 일반 누적값은 이전값에 현재값을 더해준다. 이전값이 음수라면 새로 시작하면 된다. (최대 누적합) sumR[i] = Math.max(sumR[i - 1] + num[i], sum[i - 1]); 수를 제거했을 때는 현재위치를 제거했을 때 값 sum[i-1]과 이전에 제거한 최대를 유지하고 현재를 더한 sumR[i]+num[i] 중 큰 값을 대입해주면 된다. 삽질했던 부분 수를 제거하지 않았을 때 연속되어야 한다는 생각 때문..
백준 20159 : 동작 그만. 밑장 빼기냐?
문제 링크 접근 방법 예제로 답을 구해보면서 규칙성을 찾았고 누적합 배열을 만들어서 풀이했다. 입력값인 카드의 값들은 num[]에 저장하고 순서대로의 누적합(정훈) sum[]과 뒤에서부터의 누적합(상대방) bsum[]을 구했다. 6 3 2 5 2 1 3 문제 예제의 경우 위처럼 누적합 배열을 먼저 생성하고 그림처럼 규칙에 의해 sum의 값과 bsum의 값을 더한다. 정훈이가 얻을 수 있는 카드 값의 합은 7, 8(3+5), 11(8+3), 9가 된다는 것을 알 수 있다. 하지만 이는 밑장 빼기한 카드를 정훈이가 갖는 경우만 계산한 결과이다. 카드를 밑장 빼기해서 상대방에게 주는 경우도 고려해야한다! 6 3 2 5 7 3 1 위 예제의 경우 아까처럼 계산하면 10, 11, 9, 11로 최대값이 11이 나오..
백준 20056 : 마법사 상어와 파이어볼
문제 링크 접근 방법 시뮬레이션 문제이기 때문에 문제에서 어떤 데이터가 필요한지 먼저 분석했다. 파이어볼이 이동한 후 위치에 대한 파이어볼 정보를 파악해야 했다 . → map[][]에 파이어볼의 정보를 저장 한 위치에 여러 개의 파이어볼이 존재할 수 있다. → map[][]을 리스트로 보관해야 할까? (하나로 합쳐서 저장할 수 있다) 파이어볼이 나누어지는 과정의 단순화 질량 : 파이어볼들의 질량 합에서 상수인 5로 나누기 때문에 누적해서 저장하면 된다. 속력 : 파이어볼들의 속력 합에서 개수로 나누기 때문에 누적해서 저장하고 개수를 따로 세어주면 된다. 방향 : 모두 홀수이거나 모두 짝수인 경우를 생각해야 하는데 Boolean 2개로 처리하자. 따라서 파이어볼 정보(m, s, d, cnt, odd, ev..
백준 2589 : 보물섬
문제 링크 접근 방법 최장 최단 거리이므로 BFS 결과 중 가장 큰 값을 구한다. 삽질했던 부분 트리의 지름 처음 문제에 접근했을 때 효율적으로 풀기 위해서 임의의 한 점에 대해 가장 먼 지점을 구하고, 가장 먼 지점에서부터 BFS를 수행하여 먼 곳까지의 거리를 구하면 답이 나올 수 있다고 생각했다. 즉, 트리의 지름을 구하면 답이 될 것이라고 생각했다. 하지만 문제에 주어진 보물섬이 트리가 아닐 수 있기 때문에 오답이 나왔다. 처음에는 트리가 아닐 수 있다는 점이 이해가 되질 않았는데 luniro님의 반례를 통해 이해할 수 있었다. 반례 7 7 WLLLLLW LWLWLWW LLLWLWW LWWWLWW LLLLLWW LWWWWWW WWWWWWW 우선 문제 그대로 풀이하게 되면 그림 처럼 빨간색이 보물이 ..
백준 19236 : 청소년 상어
문제 링크 접근 방법 시뮬레이션 문제이기 때문에 문제 그대로 풀었고 물고기와 상어가 이동할 때 어떤 데이터가 필요한지 먼저 분석했다. 물고기의 이동 물고기 번호 순서대로 이동이 일어나야 한다 → 번호에 따른 물고기 위치 파악 물고기의 좌표값이 교환된다 상어의 이동 좌표에 있는 물고기의 번호를 알아야 한다 → 위치에 따른 물고기 번호 파악 우선 물고기 정보(x, y, 방향)을 담는 Fish 클래스를 선언하고 정보를 관리하는 배열 Fish[]를 만들어서 물고기 번호로 위치와 방향을 알 수 있게 만들었다. 또한, int[][] map에는 해당 좌표의 물고기의 번호를 저장하였다. 물고기의 이동시 Fish[]를 순서대로 보면서 갈 수 있는 위치라면 위치를 교환해주고 방향값을 갱신하였다. 상어의 이동시 갈 수 있는..