pinevienna blog

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 문제 예전에 아주 싸해서 솔루션부터 찾아본 문제ㅋㅋ 호제야.. (백준 2609 최대공약수와 최소공배수, 1934 최소공배수 C++) 백준 2609 최대공약수와 최소공배수를 풀었다 아 뭐야 완전 쉽네~하고 그냥 뒤로 갈라는데 갑자기 싸했다 나는.. 이걸 뭔가 비효율적으로 풀 것만 같은 느낌? 그래서 그냥 바로 솔루션을 찾아봤다 pinevienna.tistory.com 한참 뒤에 이 글 쓸라니까 또 싸했음 체화시키기 위해 여러번 풀었어야 하는데.. 기회가 되면 원리에 대해 글을 써야겠다 아무튼 유클리드 호제법을 사용해 쉽게 풀 수 있다 1 2 3 4 5 6 7 8 9 10 11 12 13 #include using namespace std; i..

N의 약수의 개수와 약수가 주어질 때, N을 구하는 문제 약수의 성질을 알면 빨리 풀 수 있는 문제다 1을 제외한 가장 작은 약수와 가장 큰 약수를 곱하면 N이 됨 1234567891011121314151617181920212223include #include #include using namespace std; int main(void) { int n, res, temp; vector v; cin >> n; for (int i = 0; i > temp; v.push_back(temp); } sort(v.begin(), v.end()); if (n == 1) res = v[0] * v[0]; else res = v[0] * v[n - 1]; cout

다솜이가 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다 다솜이는 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집을 수 있다 문자열 S가 주어졌을 때, 다솜이가 해야 하는 행동의 최소 횟수를 출력하는 문제 수가 아무리 많아도 연속해 있다면 한 번에 뒤집을 수 있다 0101은 0을 뒤집든 1을 뒤집든 두 번 뒤집어야 하는데 00000000001111111111은 뭐든 한 번만 뒤집으면 된다 그럼 0000011111111111110은? 0을 뒤집는다면 두 번 뒤집어야 하지만 1은 한 번만 뒤집으면 됨 즉 연속된 수는 한 번씩만 세면서 0과 1을 count 했을 때 더 적은 수가 정답이 된다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2..

한 스키커를 떼어내면 상하좌우의 스티커는 쓸 수 없게 된다 스티커에 점수를 매기고 점수의 합이 최대한 크도록 스티커를 사용하려고 할 때 점수의 최댓값을 출력하는 문제 전형적인 DP 문제다 멋진 그림 스티커의 행이 2로 고정되어 있으니 대각선으로 -1, -2만 보면 됨 i=2, arr[0][i] + max(arr[1][i-1], arr[1][i-2]) / arr[1][i] + max(arr[0][i-1], arr[0][i-2])가 된다!! 두칸을 뛰어넘는 경우는 없으므로 다른 경우의 수는 없음 합을 누적시켜야 하므로 dp배열을 사용해서 코딩하면 된다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 3..

[백준 알고리즘/C++] 1931 회의실 배정 하나의 회의실에 최대 몇 개의 회의가 진행될 수 있는지 구하는 문제 왼쪽 열은 회의 시작시간, 오른쪽 열은 회의가 끝나는 시간이다 (첫 번째 줄 제외) 회의실이 하나이기 때문에 두 개의 회의 pinevienna.tistory.com 회의실 배정과 비슷하지만 더 어려운 문제! 강의실 배정은 최소 몇 개의 강의실이 필요한지 출력해야 한다 한 강의가 끝나기 전에 시작하는 강의는 강의실을 따로 빌려야 하고, 강의가 끝난 뒤에 시작할 경우엔 그 강의실을 이어서 쓰면 된다 찾아보니 여러가지 코드가 많았지만 priority_queue를 사용하는게 난 가장 편하게 느껴졌다 따로 빌려야 할 경우엔 pq.push / 이어서 쓸 땐 그 강의를 교체한다는 느낌으로 pop, pus..