문제https://www.acmicpc.net/problem/1149 풀이규칙이 3가지로 적혀있지만, 연속된 색깔을 사용하면 안 된다는 조건이다. 이전 값을 누적해야한다는 점에서 DP를 사용하였고, 2차원 DP 테이블을 생성하였다. 예를 들어 DP[i][0] 은 i번째 단계에서 빨간색으로 칠할 경우 누적된 최솟값이다. 만약 i 번째 단계에서 빨간색으로 칠하는 경우, i-1번째 단계에서는 초록색 혹은 파란색으로 칠해진 값들 중 최솟값을 선택하여 값을 갱신해야 한다. 이후 마지막 단계에서 최종적으로 3가지 값들 중 최솟값을 출력하면 된다. 색깔을 연속으로 사용하면 안 된다는 조건이 붙어 그리디로는 풀 수 없는 문제이다. #include using namespace std;#define MAX 1001..
문제https://www.acmicpc.net/problem/1759풀이여러 알파벳들을 통해 가능한 모든 암호를 조합해야 한다. 따라서 백트래킹 알고리즘을 사용하였다. 백트래킹을 사용하면서 생각해야할 점은지나간 단계에 대한 방문 처리를 해주어야 한다.탐색이 끝난 후에는 방문 여부를 포함하여 이전 단계로 복원시켜 두어야 한다. #include using namespace std;#define MAX 15int L, C;char arr[MAX];string S;bool check, visited[MAX];void BackTracking(int x) { if (x == L ) { int cnt1 = 0, cnt2 = 0; for (int i = 0; i = 1 && cnt2 >= 2) { cout..
문제https://www.acmicpc.net/problem/13305 풀이그리디 알고리즘으로, 현재 단계에서 취할 수 있는 가장 최선의 선택을 하는 방법으로 탐색을 진행하였다. 현재 있는 지점의 가격이 제일 쌀 경우, 해당 가격을 기준으로 하여 탐색을 진행한다. 초기값은 첫번째 주유소의 가격으로 설정한다. 2번째 주유소의 가격이 더 싸므로 price값을 2로 변경해주고, 3번째 주유소의 가격은 현재 price 값인 2보다 비싸므로 price 값을 유지한다. #include using namespace std;long long N;long long W[100000], V[100000];int main() { ios::sync_with_stdio(0); cin.tie(0); long long N, pri..
문제https://www.acmicpc.net/problem/11659 풀이누적 합을 이용하면 쉽게 풀 수 있다. i번째까지의 모든 수의 합을 담는 배열을 만든다.이후 구간 합을 구하면 되는데, 만약 구해야하는 구간이 3부터 5라면, 1번 구간부터 5번 구간까지의 합을 담고 있는 arr[5] 에서 1번 구간부터 2번 구간까지의 합을 담고 있는 arr[2] 의 값을 빼주면 된다. #include using namespace std;int arr[100001] = { 0, };int main() { ios::sync_with_stdio(0); cin.tie(0); int N, M; cin >> N >> M; for (int i = 1; i > arr[i]; arr[i] = arr[i] + arr[i -..
문제https://www.acmicpc.net/problem/1920 풀이소요 시간: 10 ~ 15분 하나 하나씩 비교할 경우 N * M 의 시간복잡도가 발생하기 때문에, 이분 탐색을 통하여 시간을 줄이면 된다. 주의할 점으로는 1. 탐색을 진행할 배열에 대해서는 오름차순 정렬을 해주어야 한다. 2. 이 문제의 경우 그래도 시간 초과가 발생하여서...... 조금 당황했다. 출력을 할 때 endl 을 사용하지 않고 개행문자를 적어줘서 문제를 해결했다. #include using namespace std;#define MAX 100001int arr[MAX];int N, M;void BinarySearch(int num) { int st = 0, en = N - 1; while (st > N; for (..
문제https://www.acmicpc.net/problem/2839 풀이소요시간 : 15분 DP로 풀었다. 각 설탕을 3kg과 5kg 단위로 묶을 수 있으니, 현재 i 단계에서 i-3 단계와 i-5 단계를 비교하여 더 적은 봉지를 사용한 DP 값으로 현재 값을 갱신한다. #include using namespace std;#define MAX 5001int DP[MAX];int main() { ios::sync_with_stdio(0); cin.tie(0); int N; cin >> N; DP[1] = -1; DP[2] = -1; DP[3] = 1; DP[4] = -1; DP[5] = 1; for (int i = 6; i 초기값 설정을...조금 많이 했다 하하........
문제 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. WOOK은 한 번에 오른쪽 또는 아래쪽으로 한 칸 이동할 수 있으며, 그 외의 방향으로 움직이는 것은 불가능하다. WOOK은 자신이 위치한 (x, y)에 자원이 있는 경우에만 해당 자원을 채취할 수 있다. WOOK이 탐사할 영역에 대한 정보가 주어질 때, WOOK이 탐색할 수 있는 자원의 최대 숫자를 구해라! 코드 DP문제이다. #include using namespace std; int board[301][301] = { 0, }; int DP[301][301] = { 0, }; int ..
문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 코드 이전에 나온 값들을 이용하여 다음 값을 도출해내는 DP문제이다. #include using namespace std; int DP[101][10]; int main() { ios::sync_with_stdio(0); cin.tie(0); long long ans = 0; int N; cin >> N; DP[1][0] = 0; for (int i = 1; i