joseph0528 코딩 블로그

보이는 거 그대로 망했다 1214라면 사실상 본선 확정이지만 이번 연도부턴 1519라 이 정도 점수론 절대 갈 수 없다. 일단 풀이는 전부터 작성하고 있었으니 이어서 작성했다. 1. 계단 더보기 nypc의 첫 문제다 처음에 잡았을 때 뇌절이 좀 있어서 나중에 풀었는데 예제 설명에 쓰여있는 방법이 최적해다.(사실 그냥 준 문제) 현재 위치에서 내려간다음 끝까지 올라갔다 내려갔다 하면서 마지막에는 현재 위치로 다시 돌아와야 하니 1층에서 지금 층으로 오는 횟수를 빼주고 뺀값들로 왔다 갔다 해주면 되는데 이때 현재 위치가 1일 때는 올라가는 거부터 해도 되지만 아닐 경우 한번 내려가 줘야 되는데 이때 위로 올라가서 횟수를 줄일 수 있을 경우 올라가 줘서 줄인 다음 내려오면 더 짧은 횟수를 구할 수 있다. 시복..

https://www.acmicpc.net/problem/17274 17274번: 카드 공장 (Large) 진서는 CTP 카드 공장의 노동자이다. 공장에는 N개의 카드가 있으며 각 카드에는 앞면과 뒷면에 숫자가 쓰여있다. 공장장 노진의 명령에 따라서 진서는 카드를 뒤집어야 한다. 명령은 M번 내려지 www.acmicpc.net 생각보다 어려웠던 문제였다 구현 자체는 오래 걸리지는 않았는데 생각하는데 오래 걸린 거 같다. 처음엔 앞면 기준 정렬된 순서로 앞면 머지 소트 트리와 뒷면 머지 소트 트리 이렇게 두 개의 트리를 만들고 구간을 다른 트리와 바꾸고 합치는 그런 방법을 생각했었는데 그럴 경우 한번 쿼리당 NlogN이라는 시복이 나와서 MNlogN으로 터지게 된다. 문제를 잘 생각해보면 M개의 입력 중에..

https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. www.acmicpc.net 간단한 세그+이분 탐색 문제이다. 처음 봤을 땐 이게 어떻게 세그로 되는 건지 싶을 수 있지만 간단한 세그로 풀수 있다. 일단 1번쿼리는 나중에 생각하고 2번 쿼리부터 보자 2번 쿼리같은경우 b맛의 사탕을 c개 넣는 거니까 b, b구간에 c를 더하는 거와 같다 마이너스여도 코드에는 변화가 없으니 그냥 한 구간에 c를 더해주면 된다. 여기까진 쉬운데 1번 쿼리에서 b번째 사탕..

https://www.acmicpc.net/problem/20149 20149번: 선분 교차 3 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 선분 교차 3은 위 문제에서 교차하는 점의 위치를 출력하는 게 더 추가된 문제이다. 그렇기 때문에 선분 교차 2를 먼저 풀고 오는걸 추천한다. 전체 코드에 대한 설명이 아닌 점위치를 찾는 코드만 설명하겠다. ..

3개월 만에 봇을 건드렸는데 3개월 사이에 솔브드 api V2가 이제 지원이 안돼서 모든 코드를 갈아엎어야 되는 상황이 왔는데 블로그 올리는 당일날 v3를 찾아서 그걸로 기존 코드는 그냥 갈아엎고 새로운 코드를 다시 짰다. 2가지 기능이 있는데 첫번째는 어떤 유저가 어떤 티어 이상의 문제를 풀었을 때 자동 알림을 오게 하는 걸 하고 싶었지만 그랬다간 시프트님께 밴 당할 거 같아서 그냥 수동으로 check를 입력했을 때만 업데이트를 하도록 해놨다 만든 이유는 다른 갓분들과 같이 있는 디코 섭에서 그럴만한 일이 있었기 때문이다. 마이너스는 개수가 줄었다는건데 주는 경우는 티어가 올랐거나 내려갔거나 아니면 없어졌거나 여러 가지 이유로 마이너스가 나올 수 있다. 두 번 째는 백준의 연습기능인데 그냥 할 게 없어..

https://www.acmicpc.net/problem/6164 6164번: Hotel The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie, ever the competent travel agent, has named the Bullmoose Hotel on famed Cumberland Street as their vacatio www.acmicpc.net 이문제는 일자로 나열된 방들이 있고 1번 쿼리는 소들은 n개가 연속되게 비어있는 방을 쓸려고 하는데 이때 그런 방이 있다면 연속된 n개..

https://www.acmicpc.net/problem/1126 1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘 www.acmicpc.net 처음에 봤을 땐 그리디로 큰 값부터 작은 위치에 값을 더하는 방식으로 하고 싶지만 그러면 틀리게 된다. 이 문제는 dp 문제인데 i번째 블록을 움직일 수 있는 경우는 왼쪽 탑에 올린다, 오른쪽 탑에 올린다, 버린다 이렇게 3가지의 경우가 있다. 이때 왼쪽 탑과 오른쪽 탑으로 분리하지 말고 왼쪽 탑과 오른쪽 탑과의 높이 차로 dp 테이블을 만들 수 있다. 그럼 이렇게 정의하자 dp ..

solved.ac 티어 : 플5 https://www.acmicpc.net/problem/22348 22348번: 헬기 착륙장 각 테스트 케이스에 대해, 한 줄에 하나씩, 빨강 페인트 a통과 파랑 페인트 b통만을 이용해 만들 수 있는 서로 다른 헬기 착륙장의 수를 109 + 7로 나눈 나머지를 출력한다. www.acmicpc.net 이문제는 dp 문제있은데 dp인걸 알기 어렵다고 한다 이 문제는 빨강 페인트 a와 파랑 페인트 b 이렇게 두 개가 입력으로 들어오면 이 두 개의 양을 넘지 않는 선에서 만들 수 있는 모든 착륙장의 경우의 수를 출력하는 문제이다. k개의 동심원인 착륙장을 만든다고 했을 때 k번째 동심원을 파랑 페인트를 칠한다고 하면 파랑 페인트는 b-k가 되고 남은 k-1개의 동심원은 a와 b..

아쉬우면서 괜찮은 결과인 거 같다. 3,4번 테케를 못 긁어서 200으로 끝났는데 그래도 1번이 dp인데 풀었다는 거와 못해도 동상은 받으니 처음 본선치곤 잘 본 거 같다는 생각이 든다(19만 원 3동 ㅋㅋㅋ) 처음에 1번을 풀다가 맞왜틀 했다가 한 가지 처리를 안 해줬다는 거를 알고 해 줬는데 그 조그마한 실수 때문에 10분 정도를 날렸고 2번은 생각은 쉬웠는데 구현이 잘 안돼서 3시간 이상을 날렸다 그다음 3번에서 조금만 긁고 4번을 갈려고 했는데 1점도 안 긁혀서 계속하다가 결국엔 200점으로 끝났다 1. 계산 로봇 위에서 말했던거처럼 dp다 어떤 점 (a, b)가 있을 때(y, x 순) |a-i|

solved.ac 티어 : 골 5 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net dp로 된다는걸 알면 쉬운데 dp인걸 알아채기가 어렵다고 해서 골 5라고 한다. 바로 문제풀이를 설명하자면 dp [i][j]=(i, j) 번째 점을 포함하는 정사각형의 한 변의 최대 길이 이게 끝이다. dp [i][j]를 구하려면 (i, j) 번째 점이 0일 때는 0이고 1일 때는 (i-1, j)==(i, j-1)==(i-1, j-1) 이면 셋 중 하나의 값+1이 dp [i][j]가 되고 아닐 떼 셋 중 가장 작은값+1을 해주면 된다..