PS하는 abra/문제 풀이
-
KOI 정리PS하는 abra/문제 풀이 2022. 10. 25. 10:25
문제가 너무 많아서 천천히 추가해나갈 예정 ★ : 응용 문제가 많은 유형? 알아두면 쓸 데 많아보이는 것들 ☆ : 너무 식상하지 않으면서 좀 재밌는 문제? (개인적으로 추천하는 것) DP는 사실 다 좋은 것 같다. 초1: 단지번호붙이기(2667) #DFS ☆초2: 숫자고르기(2668) #사이클 ★초3: 직사각형 네개의 합집합의 면적 구하기(2669) #구현 #배열에 마킹 ★중1: 연속부분최대곱(2670) #브루트포스(N 작음) #DP(N) 중2: 잠수함식별(2671) #오토마타 ★중3: 여러 직사각형의 전체 면적 구하기(2672) #좌표압축 #스위핑 고1: 잠수함식별(2671) 고2: 교차하지 않는 원의 현들의 최대집합(2673) #DP(N^3) 고3: 삼각퍼즐(2674) #백트래킹 *미해결. 풀 수 있..
-
[알고스타트] 삼각형 위의 격자점PS하는 abra/문제 풀이 2021. 5. 17. 02:05
TMI 2021 KOI 고등부 1차 대회 1교시에 출제되었던 수학 문제를 참고해 만든 문제이다. 문제 링크 https://algostart.kr/problem.php?id=1327 문제 요약 주어진 삼각형의 둘레에 놓인 점들 중 x좌표와 y좌표가 모두 정수인 점의 개수를 구하는 문제이다. 이때 삼각형의 꼭짓점의 x좌표와 y좌표는 항상 정수이다. 힌트 1. 삼각형의 세 변을 쪼개, 각 변 위에 있는 점의 개수를 구해보자. 2. 기울기 풀이 삼각형을 세 선분으로 나누어 생각하면 쉽다. 우선 각 선분에 대해 그 선분 위의 x좌표와 y좌표가 모두 정수인 점의 개수를 센다. 이렇게 구한 개수들을 더해준 후, 중복되는 점을 빼보자. (포함과 배제의 원리) 주어진 도형이 삼각형이었으므로 각 선분끼리는 삼각형의 꼭짓점..
-
[APIO 2020-A] 벽 칠하기PS하는 abra/문제 풀이 2021. 2. 11. 15:51
TMI 대회에서는 맞왜틀을 했던 문제! 구현을 좀 지저분하게 해서 맞기까지 고생을 좀 했지만(이 글을 쓰다가 깨달은 사실인데 과도한 최적화를 했기 때문에 더러워진 것이었다.) 최적화 과정에서 독특한(아님 말고) 아이디어가 사용되어 재밌었다. 이 아이디어는 다른 문제에서도 사용할 수 있을 것 같다. 문제 링크 boj.kr/19618 oj.uz/problem/view/APIO20_paint 문제 요약 N개의 구간으로 된 벽을 칠하는 데 필요한 지령의 최소 횟수를 구하는 문제. 지령(x, y): x번 일꾼이 y번째 구간을 색 C[y]로 칠하고, (x+1)%M번 일꾼이 y+1구간을 색 C[y+1]로 칠하고....이런 방식으로 M명의 일꾼이 한 구간씩 칠해, 총 M개의 구간을 칠하도록 한다. 이때 모든 일꾼에 대..