본문 바로가기

전체 글381

백준 c++ 11727 "2×n 타일링 2" -PlusUltraCode- https://www.acmicpc.net/problem/11727       [필자 사고] 동적프로그래밍이다. 필자는 dp[i]를 다음과 같이 정의하였다. dp[i] = dp[i-2]*2 + dp[i-1]; dp[i-2]의 의미는 현재 플록에서 2cm를 뺀 그동안 쌓아온 블록의 수를 의미한다. *2를 한 이유는  2cm간의 빈 공간을 어떠한 타일로 채울 것인지에 대한 의미이다. 1x2 인 형태인 타일을 위 아래로 놓는 경우의 수와  2X2 타일 한개를 넣는 경우의 수 총 2개라고 생각하여  곱셈 연산을 해주었다. 여기서 중요한 점은 2x1 타일 즉 위 아래로 기다란 타일의 경우의 수를 뺀 이유는 dp[i-1] 때문이다.  dp[i-1]은 위와 같이 1cm의 빈 곤강을 의미하므로 자동적으로 하나의 경우의.. 2024. 5. 2.
백준 c++ 11053 "가장 긴 증가하는 부분 수열" -PlusUltraCode- https://www.acmicpc.net/problem/11053       [필자 사고] 처음 문제를 보고 있을 때는 완전탐색으로 문제를 풀어 나갔다. 다만 문제가 틀리고 채점 계시판에 있는 반례를 본 후 완전탐색이 아닌 Dp로 풀기로 방향을 바꿨다. 기존 알고 있던 dp는 처음부터 차례대로 증가하는 형태로 쌓아가는 느낌이 많았다. 이 문제는 증가는 하지만 index가 작은 값들을 수시로 검사하는 형태로 쌓아가는 방식이다. dp[i] = max(dp[i], dp[k]+1) 단 i>k  이 사고만 할 수 있으면 문제를 쉽게 풀 수 있다. 다른 후기들을 찾아보니 이 문제는 LIS의 기본 문제라한다. 기본 개념이 들어간 문제이니 기억해야 겠다. [소스 코드]#include#include #include #.. 2024. 5. 1.
백준 c++ 1912 "연속합" -PlusUltraCode- https://www.acmicpc.net/problem/1912         [필자 사고]연속합 문제이다.  시간복잡도를 측정하기 위해 문제에서 주어진  N의 크기를 본 결과 N=100000이다. 즉 시간복잡도 n^2 인 형태로 코드를 짜면 안된다. 잠시 고민해본 결과 다이나믹 프로그래밍이 떠올라 해당 코드를 작성했다. 필자는 Dynamic 이라는 배열을 만들었고 Dynamic의 들어가는 숫자는 arr의 숫자들 중  순서대로 합해서 최대가 되는 숫자들만 넣는 형식으로 정의했다. [소스 코드]  #include#include using namespace std;int N;vector arr;vector Dynamic;int maxNum = -111111;void Input() { cin >> N; a.. 2024. 4. 29.
백준 14503 c++ "로봇 청소기" -[PlusUltraCode] https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽www.acmicpc.net [필자 사고]단순 구현 문제이다. 먼저 문제에서 주어진 조건들을 잘 따라오면서 코드를 작성하면 쉽게 풀릴 수 있다. 필자는 로봇이라는 객체를 하나 구현해서 문제를 풀어 나갔다.  [소스 코드]#include#include using namespace std;class Robot {public: int sero; int garo; int see; //.. 2024. 4. 25.

티스토리툴바