https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 수를 2개씩 묶거나, 더해가면서 수열의 합 중 최대 값을 찾는 문제이다. 양수를 담을 벡터 하나, 0을 담을 벡터 하나, 음수를 담을 벡터 하나 총 3개의 벡터를 활용하였다. 양수는 내림차순으로, 음수는 오름차순으로 정렬해준 뒤, 최댓값을 계산하면 된다! 먼저 양수에서는, 나의 다음 숫자가 1인 경우가 중요하다. 양수는 거의 곱하는 것이 이득인데, 1일 때는 곱하는 것보다 더하는 것이 더 이득이..
https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 이 문제.. 분명 맞게 푼 것 같은데 자꾸 시간초과가 나시는 분들이 있을 것이다. 아래 코드를 보자 if (nx = n || ny = m) continue; // 이미 방문한 경우 if (visited[nx][ny][wall]) continue; if (board[nx][ny] == 0) { q.push({nx,ny,ans..
https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net bfs문제인데, 3차원 bfs문제이다. 즉 상하좌우 + 위 아래 방향도 탐색해주면 된다. 큐에는 기존에 x,y좌표만 넣었지만, 3차원이므로 x,y좌표와 몇 층인지 해당하는 정보를 넣어주면 된다. dist배열엔 토마토가 익는 시간을 저장해주면 된다. 만약 이 dist배열에 들어있는 값이 0보다 크다면, 이미 방문했던 (=토마토가 익어버린) 곳이라는 뜻이므로 굳이 탐색하지 않는..
https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 이 문제는 단순 bfs + 약간의 구현이라고 생각한다. 16509번 장군 문제를 풀고 오시면 뭔가 비슷한데..? 라고 느끼실 수 있다. 그러나! 이 문제의 요점은 바로 원숭이가 말(馬)처럼 K번 움직일 수 있다는 것이다. 때문에 주의할 점이 2가지 존재한다. 1. 한 점에서 탐색을 할 때 말처럼 움직일 수 있으면 말처럼 움직이고, 상하좌우 탐색도 같이 해줘야한다는 것! 2. 아래 ..
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 오랜만에 푼 DP(다이나믹 프로그래밍)문제다. 우선 삼각형을 입력 받아준다. 입력값들의 길이가 1,2,3,... 순으로 증가하므로 2차원 벡터를 이용해 입력 받았다. 그런 다음, 초기값을 설정해주는 것이 중요한데 dp[1][0]은 삼각형의 맨 첫번째 값(=꼭대기 값)이고 dp[1][1]은 원래 존재하지 않는 값이지만 점화식을 생성 및 이용하기 위해 0으로 설정해주었다. 초기값(삼각형 1층)에 대한 설정이 끝났으므로, 그 아래 줄인 삼각형 2층부터 점화식을 이용해 최대값..
https://www.acmicpc.net/problem/16927 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 이 문제는 얼핏 보면 아래 소스코드처럼 특정한 규칙을 찾아서 전부 탐색하여 배열을 돌려주면 풀릴 것 같지만, r의 입력이 최대 10억이므로, 10억번 반복을 하면 O(n)의 시간복잡도를 가질지라도 1초를 넘기게 되므로 시간초과가 뜬다! 해결 -> 덱(deque)에 넣어서 돌리자! 양파껍질까듯 바깥의 ..
