백준알고리즘15 [BOJ]2096번: 내려가기 문제: https://www.acmicpc.net/problem/2096 슬라이딩 윈도우 문제입니다. 메모리 제한이 심상치 않습니다. 발판은 board[N][3]의 형태를 가지고 있지만, i번째 칸을 계산함에 있어서 필요한 발판정보는 i-1번째 칸의 정보만 필요합니다. 그러므로 메모이제이션을 위한 dp[][] 배열이나 input값을 저장하는 board[][] 배열 모두 [2][3] 크기면 됩니다. dp배열을 다음과 같이 정의내리겠습니다. max_dp[N][M]: 맨 윗칸에서부터 board[N][M] 칸까지 내려왔을 때 얻을 수 있는 최댓값 min_dp[N][M]: 맨 윗칸에서부터 board[N][M] 칸까지 내려왔을 때 얻을 수 있는 최솟값 끝으로 dp[i][], dp[i+1][] 이렇게 두 칸만 사용하.. 2020. 7. 22. [BOJ]14889번: 스타트와 링크 문제: https://www.acmicpc.net/problem/14889 시뮬레이션 문제입니다. C++ 기준 넥퍼뮤를 사용해서 두 팀으로 나눈 후, 팀을 나눈 각 경우마다 능력치값을 구해서 최소값을 구하도록 했습니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ14889.cc 2020. 7. 20. [BOJ]13913번: 숨바꼭질 4 문제: https://www.acmicpc.net/problem/13913 매 같은 초마다 여러 방향으로 움직일 수 있으므로 BFS문제입니다. 특정좌표 X에서, X+1, X-1, 2*X 이렇게 BFS탐색을 해주면 됩니다. 그리고 한 가지 처리해줘야 할 특수 케이스는 수빈이의 좌표가 동생의 좌표보다 큰 경우, 무조건 X-1을 통해 이동해야합니다. 이 경우 X-1로만 움직일 수 있는데 불필요하게 BFS 탐색을 하게 되면 시간초과가 납니다. 이 부분만 유의하시면 될 것 같습니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ13913.cc 2020. 7. 14. [BOJ]16988번: Baaaaaaaaaduk2 (Easy) 문제: https://www.acmicpc.net/problem/16988 시뮬레이션 문제입니다. NM에 대해서 돌을 둘 2개의 좌표를 구하면 됩니다. 탐색 후보를 줄이려다보니 코드가 길어졌네요ㅠㅠ 1. 상대방 돌과 인접한 4칸 중 빈 칸을 탐색 후보칸으로 두기 2. 탐색 후보 칸 중에 2칸을 뽑아서(nCr) 내 돌 두기 3. 상대방 돌이 뭉쳐있는 컴포넌트 중에, 컴포넌트와 인접한 칸 중에 빈 칸이 하나도 없으면 이 컴포넌트는 죽은 컴포넌트입니다. 이렇게 죽은 컴포넌트 갯수의 합을 구해서 최댓값으로 갱신해주면 됩니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ16988.cc 2020. 7. 10. 이전 1 2 3 4 다음
