김머성 블로그

[BAE/<JOON> 문제풀이] 2869. 달팽이는 올라가고싶다

https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) 출력 첫째 줄에 달팽 www.acmicpc.net 원래 10844번 풀어야되는데 오늘 정해진 시간안에 못풀어서 저번에 푼 문제로 땜빵함... 수식으로 풀어야함. 구현으로는 ..

[BAE/<JOON> 문제풀이] 1912. 연속합 (DP.009)

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 개인적으론 계단이나 와인문제보단 쉬운 문제 같다. 이전 숫자까지의 최대합을 계산하고 계속 더해나갈 것인지 아니면, 끊고 새로운 최댓값을 찾을 것인지만 결정하면 된다. (이전 문제들처럼 이전 노드의 상태를 검사할 필요가 없었다.) 더보기 #include #include using namespace std; int main() { int n; cin >> n; vector arr; vector dp; arr.r..

[BAE/<JOON> 문제풀이] 2156. 포도주 시식 (DP.008)

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net 저번의 계단문제와 비슷한 문제다. 구현도 거의 비슷하게 했는데 한가지 다른 점이 계단 문제에서는 무조건 2칸안의 계단을 밟아야만 했지..

[c++/boost::asio] Bank Server 개발일기

정해놨던 클라이언트 연결 방식을 실제로 구현하고 있다. 우선 DB쪽은 개설하기도 어렵거니와 따로 공부를 해야하는 파트이기 때문에 return true함수를 만들어 사용하고 있고 나머지 큐작업~ 실제 통신까지 구현을 했다. 우선 나는 이 프로그램을 수많은 사용자가 사용할 것이고 여러대의 컴퓨터에서 이 프로그램을 가동해서 io를 처리한다는 가정하에 개발을 진행하고 있다. 그렇다보니 쓰레드 작업이 가끔 여러번 겹쳐서 복잡해 질 때가 있다. 지난번에 작성했던 포인터 손실 현상도 사실 쓰레드에 관련된 문제였다. 이번엔 오늘 발생했던 쓰레드 프로그래밍에 대한 기본적인 실수를 적어보려한다. while (stop_ev_.wait_for(std::chrono::microseconds(100)) == std::future..

[BAE/<JOON> 문제풀이] 1932. 정수 삼각형 (DP.007)

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 www.acmicpc.net 이런 종류의 트래킹 문제는 확실히 DP가 좋은 해결법이다. 이거 백트래킹하면 100개 사이즈 정도만 되도 시간 초과가 발생할 것이다. ..

[BAE/<JOON> 문제풀이] 2193. 이친수 (DP. 006)

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되 www.acmicpc.net 더보기 #include #include using namespace std; int main() { int n; vector arr; ci..