PS/BOJ
BOJ 11054 가장 긴 바이토닉 부분 수열
boj 11054 가장 긴 바이토닉 부분 수열 boj 11503 가장 긴 증가하는 부분 수열 문제를 풀었다면 쉽게 이해할 수 있는 문제이다. 아래의 풀이를 참고할 것을 추천한다. boj 11503 가장 긴 증가하는 부분 수열 문제 풀이 바이토닉 수열이 기준이 되는 수를 중심으로 증가하는 수열에서 감소하는 수열로 바뀐다는 것에 포인트를 잡았다. 바이토닉 수열의 길이의 최댓값 = (기준 수까지 증가하는 수열 길이 + 기준 수부터 감소하는 수열 길이)의 최댓값라고 이해할 수 있다. Dinc[i]는 i를 마지막 원소로하는 증가 수열 길이의 최댓값이고, Ddec[i]는 시작 원소를 i로 하는 감소 수열 길이의 최댓값이다. 쉽게 구현하기 위해 Ddec[i] 표현을 달리해보자. 수열이 담긴 배열 a[i]를 거꾸로 끝..
BOJ 11722 가장 긴 감소하는 부분 수열
boj 11722 가장 긴 감소하는 부분 수열 boj 11053 풀이 보기 boj 11053 문제에서 증가하냐 감소하냐의 차이만 있을 뿐 다른 것은 다 똑같은 문제이다. 그렇기에 점화식을 실행하는 2가지 조건 중 a[i] > a[j]만 a[i] > n; for (int i = 1; i > a[i]; for (int i = 1; i = D[i]) D[i] = D[j] + 1; } mx = max(mx, D[i]); } cout
BOJ 11055 가장 큰 증가 부분 수열
boj 11055 가장 큰 증가 부분 수열 boj 11053 가장 긴 증가하는 부분 수열과 풀이가 비슷한 문제이다. 다만 11053에서는 길이였다면 이번 문제에서는 수열의 합이 최대가 되어야한다. D[i]는 i번째 원소를 마지막으로 하는 증가 부분 수열의 합 중 최댓값이라고 정의한다. a[i]는 수열을 담는 배열이다. 문제에서 주어진 수열을 예시로 들자면, 아래와 같이 작동해야한다. 코드를 먼저 보고 코드에 대해 설명하겠다. #include #include using namespace std; int n; int a[1005]; int D[1005]; int mx; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int ..
BOJ 11053 가장 긴 증가하는 부분 수열
boj 11053 가장 긴 증가하는 부분 수열 D[i]가 어떻게 작동해야 문제에서 원하는 답을 잘 찾아낼 수 있을까를 생각해봤다. 위 그림과 같이 작동해야하는데, 그래서 D[i]를 i번째 원소를 마지막으로 하는 가장 긴 부분 수열의 길이라고 정의하였다. a[i]는 수열을 담는 배열이다. D[i]는 길이이기에 1씩 점점 증가하는 방식으로 식을 정의해줘야하는데, 언제 1씩 증가시켜야하는지 조건을 정해주는 것이 이 문제의 핵심이다. 먼저 코드를 보고 코드에 대해 설명해보겠다. #include #include using namespace std; int n; int mx; int a[1005]; int D[1005]; int main(void) { ios_base::sync_with_stdio(0); cin.t..
BOJ 7576 토마토
boj 7576 토마토 BFS로 풀 수 있는 문제다. 조금 독특한 점은 시작점이 여러 곳이 될 수 있다는 것이다. 전체를 다 돌아보고 시작점이 될 수 있는 곳을 다 찾아 한번씩 bfs를 다 돌려보는 풀이가 가장 먼저 생각났지만, 최대 시간복잡도가 O((NM)^2)이 될 수 있어 이 방법으론 풀 수 없다. 그래서 토마토 정보를 입력받을 때, 익은 토마토의 시작점을 전부 큐에 넣어주고 bfs를 돌리는 방식으로 문제를 풀었다. 익은 토마토의 경우 거리 dis 값이 전역변수이니 0으로 채워지고, 안 익은 토마토는 dis 값을 -1로 둔다. 코드를 한번 보자. #include #include #include #include using namespace std; int n, m; int board[1005][100..