🔗 문제 링크https://www.acmicpc.net/problem/1188💡 문제 풀이 및 해석최대공약수를 구하는 문제이자 패턴 문제이다. 모든 소시지를 합쳐서 1개로 만들고 균일하게 자른다고 생각하면 된다. 이 때, 소시지를 합치는 자리를 칼질하는 경우만 카운팅을 안하면 된다.예제 2번 케이스에서 3 4 => 인당 3/4가 필요하다는 뜻이고, 이는 소세지 3개를 이어 붙여서 1개로 만든 다음에 4등분하면 된다는 뜻이다. 따라서 3번만 자르면 된다.다시 예제 1번 케이스를 보자 2 6 이 들어오고 인당 2/6이 필요하다. 이는 소세지 2개를 이어 붙여서 1개로 만든 다음에 6등분하면 된다는 뜻인데, 그러면, 총 5번의 칼질 중 1번의 칼질은 카운팅할 필요가 없다. 이는 최대공약수로 나타낼 수 있다..
G4
🔗 문제 링크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를 더한다..
🔗 문제 링크 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];..
🔗 문제 링크 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 💡 문제 풀이 및 해석 만약 카드의 숫자가 N개라면 반드시 N-1번의 계산을 해야 한다. 여기서 가장 적은 수를 더해야 한다. 항상 가장 작은 두 집합을 더해준다. 이러면 결과적으로 가장 작은 수가 나온다. 만약, 큰 수가 들어가게 된다면, 그 수는 총 연산에서 이번 연산을 제외하고 반드시 한번 더 들어가야 하므로 최소값이 될 수 없다. ⭐️ 정답 코드 및 설명 #include #include using namespace std; i..
🔗 문제 링크 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 💡 문제 풀이 및 해석 원형이 PPAP 인지 확인해야 하는 문제다. P -> PPAP 이므로 역으로 생각하면 PPAP -> P 가 된다고 생각할 수 있다. 그럼 문자열에서 앞에서부터 PPAP 인 부분을 P 로 바꿔가면서 O(N) 으로 탐색하면 된다. ⭐️ 정답 코드 및 설명 #include #include using namespace std; string sol(string str) { string temp = ""; int tempIndex = 0; for (int i = 0; i < str.siz..
🔗 문제 링크 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 💡 문제 풀이 및 해석 최소한의 인원을 이동시키면서 줄을 세워야 하는 문제이다. 줄을 세운다 => 숫자를 정렬한다 => 정렬할 때, 최대한 적게 움직여야 한다. 움직이는 인원 = 전체 - 움직이지 않아도 되는 인원 움직이지 않아도 되는 인원 = 이미 줄이 제대로 돼있는 인원 따라서 이미 정렬이 되어있는 인원을 전체에서 빼주면 된다!! 내 위치에서 내 앞에 있는 인원들을 비교하여 나까지 증가하는 부분 수열을 구하면 된다. ⭐️ 정답 코드 및 설명 impor..
