전체 글
백준 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..