🔗 문제 링크 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]..
🔗 문제 링크 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 💡 문제 풀이 및 해석 블루레이의 사이즈는 최대 10억이다. 따라서 최대 크기를 10억으로 잡아두고 시작한다. 블루레이의 사이즈를 이분탐색으로 정한다. 블루레이에 담기는 순서는 강의의 순서와 같으므로, 순서대로 블루레이에 강의를 담는다. 그렇게 블루레이가 꽉 차면 다음 블루레이에 담기는 순서로 이분탐색을 진행하면 된다. ⭐️ 정답 코드 및 설명 #include #include using namespace std; int N, M; vector lectur..
🔗 문제 링크 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 💡 문제 풀이 및 해석 치킨집은 13개 이하, 그냥 집은 최대 2N 이다. 조합으로 13개를 뽑는다면, 최대 13C6 이다. 따라서 1716 * 2 * 50 이므로 브루트포스하게 풀 수 있다. 이제 치킨집을 고른 뒤, 집마다 치킨집까지의 거리를 구하고 가장 가까운 거리를 계속 더해주면 된다. ⭐️ 정답 코드 및 설명 #include #include #define INF 987654321 using namespace std; in..
🔗 문제 링크 https://www.acmicpc.net/problem/9251 💡 문제 풀이 및 해석 '최장 부분 공통 수열' 문제는 DP를 사용한다. 어떻게 풀지 모르겠어서 구글링을 하여 아래 사이트에서 이해를 한뒤 풀었다. 주석을 풀면 myMap이 만들어진 것을 볼 수 있다. 도움을 받은 사이트 ⭐️ 정답 코드 및 설명 #include #include using namespace std; string str1, str2; //string answer = ""; int myMap[1001][1001]; void input() { cin >> str1 >> str2; } int sol() { for (int y = 1; y
