푸키키키

문제

app.codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/

풀이

첫번째 생각

1. 전체의 부분합을 구한다.
2. A, C 를 뽑는 모든 경우의 수를 구해서 계산한다.
3. 부분합[C-1] - 부분합[A] 으로 A+1 ~ C-1 까지의 부분합 구한 후 이 사이를 B라고 생각하고 하나씩 빼보면서 답을 구한다.

=> A, C를 뽑는 조합은 nC2 로 N제한이 10만이어서 10만 * 10만 으로 쉽게 시간초과가 날 것 같다.

두번째 생각

1. 왼쪽에서 오른쪽 방향으로 Largest Sum Contiguous Subarray 을 구한다.
2. 오른쪽에서 왼쪽 방향으로 Largest Sum Contiguous Subarray 을 구한다.
3. B를 2~C-1이라고 생각하고 B-1까지 왼쪽에서 오른쪽방향의 LSCS 가 계산하고 B+1에서 N-1까지 오른쪽에서 왼쪽 방향으로 LSCS가 계산해서 for문을 한번 돈다.

=> 이렇게 하면 B를 지정해주는 for문만 돌면 되므로 O(N)만에 해결할 수 있었다.

코드

function solution(A) {
  let increaseArray = new Array(A.length).fill(0);
  let decreaseArray = new Array(A.length).fill(0);

  for (let i = 1; i < A.length - 1; ++i) {
    increaseArray[i] = Math.max(increaseArray[i - 1] + A[i], 0);
  }
  for (let i = A.length - 2; i > 0; --i) {
    decreaseArray[i] = Math.max(decreaseArray[i + 1] + A[i], 0);
  }
  let ans = -9999999;

  for (let i = 1; i < A.length - 1; ++i) {
    ans = Math.max(increaseArray[i - 1] + decreaseArray[i + 1], ans);
  }
  return ans;
}

문제

https://www.acmicpc.net/problem/9184

풀이

정의대로 코드 작성한 후 메모이제이션 한다.

코드

let fs = require('fs');
// let input = fs.readFileSync('/dev/stdin').toString().split('\n');
let input = fs.readFileSync('./b9184.txt').toString().split('\n');

let readlineIdx = 0;

const readInput = () => input[readlineIdx++];

const fillMax = 0;
let table = new Array(21);

function w(a, b, c) {
  if (a <= 0 || b <= 0 || c <= 0) {
    return 1;
  }

  if (a > 20 || b > 20 || c > 20) {
    return w(20, 20, 20);
  }

  if (table[a][b][c] !== fillMax) {
    return table[a][b][c];
  }

  if (a < b && b < c) {
    let t1 = table[a][b][c - 1] = w(a, b, c - 1);
    let t2 = table[a][b - 1][c - 1] = w(a, b - 1, c - 1);
    let t3 = table[a][b - 1][c] = w(a, b - 1, c);
    return table[a][b][c] = t1 + t2 - t3;
  }


  let t1 = table[a - 1][b][c] = w(a - 1, b, c);
  let t2 = table[a - 1][b - 1][c] = w(a - 1, b - 1, c);
  let t3 = table[a - 1][b][c - 1] = w(a - 1, b, c - 1);
  let t4 = table[a - 1][b - 1][c - 1] = w(a - 1, b - 1, c - 1);
  return table[a][b][c] = t1 + t2 + t3 - t4;

}

function main() {
  for (let i = 0; i < 21; ++i) {
    table[i] = new Array(21);
    for (let j = 0; j < 21; ++j) {
      table[i][j] = new Array(21).fill(fillMax);
    }
  }
  while (true) {
    let [a, b, c] = readInput().split(' ');
    a = Number(a);
    b = Number(b);
    c = Number(c);
    if (a === -1 && b === -1 && c === -1) break;
    console.log(`w(${a}, ${b}, ${c}) = ${w(a, b, c)}`);

  }
}

main();

문제

https://www.acmicpc.net/problem/1913

풀이

1, 1 부터 시작해서 반시계방향으로 배열 만들어 간다.
만들다가 해당 숫자 나오면 좌표를 기록한다.
배열이 완성되면 배열과 좌표를 출력한다.

코드

let fs = require('fs');
// let input = fs.readFileSync('/dev/stdin').toString().split('\n');
let input = fs.readFileSync('./b1913.txt').toString().split('\n');

let readlineIdx = 0;

const readInput = () => input[readlineIdx++];

let dx = [0, 1, 0, -1];
let dy = [1, 0, -1, 0];
let answerLoca = { X: 0, Y: 2 };
function solution(table, t) {
  let cnt = t * t;
  let X = 0;
  let Y = 0;
  let nowDir = 0;
  let moveCnt = t;
  while (true) {
    if (nowDir === 1) {
      moveCnt--;
    }
    if (nowDir === 3) {
      moveCnt--;
    }

    for (let i = 0; i < moveCnt; ++i) {
      X = X + dx[nowDir];
      Y = Y + dy[nowDir];
      table[X][Y] = cnt--;
      if (table[X][Y] === findNum) {
        answerLoca = { X, Y };
      }
    }


    if (cnt === 0) {
      return;
    }
    nowDir = (nowDir + 1) % 4;
  }
}

let findNum;
function main() {
  let t = readInput();
  t = parseInt(t, 10);
  findNum = parseInt(readInput(), 10);
  let table = new Array(t + 1);
  for (let i = 0; i < t + 1; ++i) {
    table[i] = new Array(t).fill(0);
  }
  solution(table, t);
  for (let y = 1; y < t + 1; ++y) {
    let string = "";
    for (let x = 0; x < t; ++x) {
      if (x === t - 1) {
        string += table[x][y];
        break;
      }
      string += table[x][y] + ' ';
    }
    console.log(string);
  }
  console.log(answerLoca.Y, answerLoca.X + 1);

}

main();