🔗 문제 링크 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..
baekjoon
🔗 문제 링크 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];..
🔗 문제 링크 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 💡 문제 풀이 및 해석 처음에는 평균을 잡아놓고, 평균 아래의 가격과의 차액을 더하는 방식으로 할려 했지만, 차액을 더하는 도중에 평균보다 위였던 금액이 평균보다 낮아져 버릴 수도 있음을 알았다. 그래서 차라리 이분탐색으로 금액을 정해놓고 이 금액이 가능한지 판별하는 방식으로 접근하기로 했다. 만약 전체 금액 N; country = vector(N); for (int i = 0; i > country[i]; su..
🔗 문제 링크 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 💡 문제 풀이 및 해석 일단, 보자마자 비싼 강의를 최대한 많이 들어야 한다는 것을 알 수 있다. 여기서 어떻게 들어야 할 것인가가 중요하다. 여기서 day로 정렬해서 한다면, 문제가 발생한다. 예를 들어서, 같은날 비싼 2개의 강의가 있을 때, 전날 강의를 버리고 그 다음날까지 유예기간이 있는 강의를 들을 수가 없기 때문이다. 여기서 해결방법으로는 아래와 같다. 가장 비싼 강의로 내림차순으로 정렬한다. 유예기간..
🔗 문제 링크 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 💡 문제 풀이 및 해석 N > N; dp = new int[N + 1]; building.push_back({ -1,-1 }); for (int i = 1; i > left >> right; building.push_back({ left,right }); dp[i] = 1; } sort(building.begin(), building.end()); } void sol() { int answer = 0; for (int i = 1; i building[j]..
