🔗 문제 링크https://www.acmicpc.net/problem/1034💡 문제 풀이 및 해석처음에는 50X50의 문제여서 완전탐색으로 풀 수 있는 문제라 생각했는데, 1000번의 열의 스위치를 킬 수 있다는 선택지 때문에, 2^50의 가짓수라 모든 경우를 찾아볼 수 없는 문제였다.문제의 조건을 보았을 때, K번을 반드시 눌러야 하므로 예제에서 열이 1개일 때, 짝수번이면 변화가 없는 것을 알 수 있다. 이 점에 유의해야 한다.모든 경우를 찾을 수 없다면, 경우를 줄여야 하는데, 이때, 패턴을 찾는 것이 그 방법이다. 예를 들어서 100 100 101 110 이런 식이라고 하자. 100과 101, 110은 같은 열의 솟자가 바뀌기 때문에 최종적으로 모두 1인경우가 나올 수가 없다. 따라서 100..
알고리즘 문제 풀이
🔗 문제 링크https://www.acmicpc.net/problem/11054문제 링크가 제대로 달리지 않아 링크 남겨두었습니다.💡 문제 풀이 및 해석어떤 특정한 수를 기준으로 양쪽에서 증가하는 수열을 찾아야 한다.N의 범위가 1000 이므로 한번에 검사하는 것이아닌 왼쪽과 오른쪽으로 증가하는 수열을 따로 찾아도 된다.한쪽으로 증가하는 부분 수열을 찾는 방법은 아래와 같다.현재 index가 K라면, 0~K-1 까지의 수들을 모두 탐색한다.이 때, K보다 작은 수들을 찾는다.그 중에서 DP[찾은 수] + 1 > DP[K]라면 증가하는 부분 수열이므로 업데이트 해준다.찾은 모든 수들에 대해서 3번을 반복하면 DP[K]가 최댓값을 갖는다.위 방식으로 좌우를 했을 때, rightDp와 leftDp를 더한다..
🔗 문제 링크 14728번: 벼락치기ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와www.acmicpc.net💡 문제 풀이 및 해석가치에 따라서 결정하는 냅색 문제이다.우리가 최대로 가져가야 하는 것은 점수이고, 그 비용은 시간이 된다.최대로 가져갈 수 있는 점수는 dp[T]에 있다. 이 때, 역순으로 다이나믹 프로그래밍을 진행한다.dp는 그 시간대의 최대값이므로 검사할 시간이 t라면, dp[t] = max(dp[t], dp[t - time] + score)는 t-time 이 그 시간에서 최대이고 현재 값을 더하면..
🔗 문제 링크 11660번: 구간 합 구하기 5첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네www.acmicpc.net💡 문제 풀이 및 해석누적합 문제로써 매번 계산하면 안 되는 문제다.이미 누적이 된 상태에서 상수시간으로 각각의 케이스를 해결해야 한다.수학적으로 부분구역은 acc [ey][ex] + acc [sy - 1][sx - 1] - acc[sy - 1][ex] - acc [ey][sx - 1] 이미 누적된 데이터만 있으면 상수 시간 안에 해결이 가능하다.누적된 데이터는 acc [y][x]=myMap [y][x]+ac..
🔗 문제 링크 2531번: 회전 초밥첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤www.acmicpc.net💡 문제 풀이 및 해석일단, 브루트포스로 할시 3000 * 30000으로 9천만 번의 실행을 해야 하는데, 이론상 1초 안에 가능하지만, 실제 해보니 시간초과가 났다. (아마, 메서드를 불러오고 입출력에서 시간을 쓰이는 것 같다.)브루트포스하게 해결할 수 없다. 따라서 다른 방법을 생각해야한다.'연속'하는 회전초밥을 먹었고, 추가적으로 한 접시를 더 주는 조건이 이미 있다.매번 연속..
🔗 문제 링크 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 💡 문제 풀이 및 해석 일단, 맵의 크기와 반복 횟수가 5인 점을 감안하면 브루트 포스하게 풀 수 있다고 생각했다. (매번 맵을 복사 하면서) 상하좌우 움직이는 모형을 구현해야 한다. 2-1. 순서대로 이동하는 것이니 0을 제외하고 모두 받아온다. 2-2. 순서대로 쌓아 올린다. 2-3. 이때, 같은 칸(같은 index)에 쌓아 올릴 때, 같은 숫자면 더해주고 다음 칸으로 넘어간다. 2-4. 칸은 칸에 쌓아 올릴 때, 다..
🔗 문제 링크 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 💡 문제 풀이 및 해석 문제를 보고 바로 다익스트라인 것을 알았다. (양수 가중치, 최단거리가 아닌 가장 비용이 낮은 거리) 먼저 이동할 Map을 만드는데, 이동에 필요한 cost와 지금까지의 비용인 dist를 넣어주었다. 나머지는 다익스트라 알고리즘에 맞게 dist가 갱신될 수 있을 때마다 갱신해주면서 넣어주었다. 단, 0인 지점은 아직 방문한적이 없을 때, (dist == INF) 이동할 수 있게 하였고, 그 이후에는 3번과정..
🔗 문제 링크 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 💡 문제 풀이 및 해석 모든 data를 받아올 때, 빈칸(0)만 따로 받아온다. 빈칸에 숫자 1~9가 들어갈 수 있는지 판별한다. (가로, 세로, 섹터) 2-1. 넣을 수 있다면 넣은 다음 다음 칸으로 넘어간다. 2-2. 아무 숫자도 넣을 수 없다면 변경사항을 취소하고, 뒤로 돌아간다. 모든 빈 칸이 채워질 때까지 반복한다. ⭐️ 정답 코드 및 설명 #include #include using namespace std; int myMap[9][9];..
