🔗 문제 링크https://www.acmicpc.net/problem/21610💡 문제 풀이 및 해석시뮬레이션 문제인 만큼 문제의 조건을 그대로 구현하면 된다.이 전에 비가 내린 것을 구분하는 것은 MAP 구조체를 만들어서 isRain으로 판별하였고, next_x,next_y의 99값은 문제의 조건대로 Index를 1부터 쓰기 위함이다. 정확한 방식은 아래와 같다.이동하기 전에, 맵에 isRain을 모두 false로 만들어준다. (처음엔 상관없지만, 한 바퀴 돈 뒤에는 기존에 비가 내렸던 곳의 마킹을 없애주기 위함이다.)방향 * 거리 만큼 이동시킨다.이동시킨 거리를 N으로 나눈 나머지를 구한다. (위치 특정을 위해) 이때, -로 이동하거나 만약 N의 위치에 있다면 0 이하이므로 0 이하이면 N을 더해..
G5
🔗 문제 링크 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 이 그 시간에서 최대이고 현재 값을 더하면..
🔗 문제 링크 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]..
🔗 문제 링크 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
🔗 문제 링크 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 💡 문제 풀이 및 해석 주어진 단어중 정해진 갯수를 뽑는 조합문제이다. 조합으로 뽑은 다음에, 모음이 1개 이상, 자음이 2개 이상 들어갔는지 체크해주면 됩니다. ⭐️ 정답 코드 및 설명 #include #include #include #include using namespace std; int L, C; bool visit[15]; vector word; set answer; void input() { cin >> L >> C; word = vecto..
🔗 문제 링크 https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 💡 문제 풀이 및 해석 주어진 조건이 뒤에 'A'를 붙이는 것과 'B'를 붙이고 뒤집는 것이다. 최악의 조건을 생각해보자. S.size() = 1, T.size() = 50 이다. 여기서 S -> T 로 갈 때, 브루트포스하게 할 수 없다. 2의 50제곱은 좀 많이 크다. S -> T 로 갈 때, 조건을 설정해주면 어떨까?? 이 문제는 사실 ..
🔗 문제 링크 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 💡 문제 풀이 및 해석 문제부터 선수과목이라고 써져 있는 것을 보니, 위상정렬 문제임을 알 수 있다. (많이 풀어본 경험으로써??) 위상정렬이라고 마냥 어렵게 생각할 것 없다. 과목 A를 해결하면 과목 B를 배울 수 있다는 조건을 보자. A -> B 라고 생각하자. 그러면 화살표를 받는 B는 선수과목의 숫자가 +1이 되는 것이다. 그러면, 이는 선수과목의 숫자가 0이라면 수강할 수 있다는 뜻이 되기도 한다. 3번 해석을 input()에 적용시켰다. X가 선수과목해야 하는 숫자..
