알고리즘/IUPC 2022 (6) 썸네일형 리스트형 [백준] 25210번 정사각형 세기 [C++] https://www.acmicpc.net/problem/25210 접근 방식 먼저, 정사각형의 꼭짓점이 될 수 있는 구간을 정한다. 회전하지 않은 정사각형이 되야 하기 때문에, 빨간색 외의 부분은 점으로 선택되지 못한다. 따라서 이러한 부분을 없애준다. 두번째로 남은 부분에서, 좌 우 상 하 범위를 한정시켜 놨기 때문에, 1사분면과 3사분면만 생각해준다. 마지막으로 정사각형을 만들기 위해서, y=x+k(k는 문제의 범위인 -100000~100000) 형태의 그래프를 그려준다. 이 그래프가 1사분면의 정사각형에서 만나는 점 N개, 3사분면 정사각형에서 만나는 점 M개가 있다면, 이 때 그릴수 있는 정사각형의 개수는 N*M개 일 것이다. 이러한 과정을 모든 K에 대해서 해준 후 계산을 하면 답을 구할 수 .. [백준] 25216번 파밍루트 [C++] https://www.acmicpc.net/problem/25216 25216번: 파밍 루트 경태는 인하대학교에서 유행하는 게임 Conquer The Planet(이하 CTP)에 빠져있다. CTP를 열심히 플레이하던 어느 날, 경태는 게임 속에 숨겨져 있던 던전을 발견했다! 던전 입구에는 플레이어를 위한 설 www.acmicpc.net 문제 접근 방법 우선 방어력에 초점을 두지 말고, 내가 구할 수 있는 가장 많은 금화의 양을 계산을 해야한다. 방어력을 max값으로 두고,어느 지점에서도 막히지 않게 한다면 주어진 시간동안 구할 수 있는 가장 많은 금화를 구할 수 있다. 이는 다이나믹 프로그래밍 방법으로 구하게 됐는데, DP[남은 시간][현재 위치]=max(DP[남은시간 - 1][현재 위치에서 갈 수 있는.. [백준] 25208번 새벽의 탐정 게임 [C++] https://www.acmicpc.net/problem/25208 25208번: 새벽의 탐정 게임 새벽의 탐정 게임은 재미있는 2인용 보드게임이다. 한 명은 탐정, 다른 한 명은 도둑 역할을 맡는다. 게임은 $N$행 $M$열 격자 위에서 진행된다. 격자의 각 칸은 벽이 설치되어 있거나 비어있고, 역 www.acmicpc.net 문제 문제 요약 문제가 너무 김에 따라서 요약을 하자면, 위와 같은 판에 도둑, 탐정 두가지가 있는데, 탐정은 상하좌우 4가지 방향 중 한곳으로 움직일 수 있다. 탐정은 위의 전개도로 만들어지는 감옥을 본인 시작 지점에서 바닥이 뚫린 채로 시작하며, 움직이는 방향에 따라서 주사위처럼 비어있는 부분또한 움직이게 된다. 도둑을 가두기 위해서는 도둑이 있는 지점에 감옥의 바닥이 뚫린 .. [백준] 25215번 타이핑 [C++] https://www.acmicpc.net/problem/25215 25215번: 타이핑 민겸이는 영어 소문자와 대문자로 이루어진 문자열을 타이핑하기로 했다. 민겸이가 사용할 수 있는 버튼은 26개의 영어 알파벳 버튼과 마름모(◆) 버튼, 별(★) 버튼이다. 각 버튼은 아래와 같이 www.acmicpc.net 문제 설명 먼저 각 각 경우를 생각해야 한다. aaAaa 와 같이 소문자들 사이에 대문자가 1개 있을 경우, aaa★aa->6번만에 해결 가능 aa◆a◆aa->7번만에 해결 가능 aaAAa와 같이 소문자들 사이에 대문자가 2개 있을 경우, aaa★a★a->7번만에 해결 가능 aa◆aa◆a->7번만에 해결 가능 aAAAa와 같이 소문자들 사이에 대문자가 3개 있을 경우, aa★a★a★a->8번만에 해.. [백준] 25212번 조각케이크 [C++] https://www.acmicpc.net/problem/25212 25212번: 조각 케이크 조각 케이크들을 골랐을 때, 고른 조각 케이크를 모두 합쳐서 케이크 한 판으로 만들 수 있는 경우의 수를 출력한다. www.acmicpc.net 문제 설명 접근 방법 조각 케이크의 갯수가 최대 10개기 떄문에 브루트포스 방식을 사용해 모든 경우의수를 찾아내도 자원소모가 크지 않다. 따라서 브루트포스 방식을 통해 각각 경우마다 케이크 조각들의 총 합이 101/100(1.01)을 넘어갈 경우에 더 탐색을 하지 않고, 총 값이 101/100 와 99/100 사이에 있다면 탐색을 하지 않고 결과값을 1 늘린다. 이러한 방식대로 모든 경우를 다 탐색하면 가능한 모든 경우를 찾을 수 있다. #include #include.. [백준] 25214번 크림 파스타 [C++] https://www.acmicpc.net/problem/25215 25215번: 타이핑 민겸이는 영어 소문자와 대문자로 이루어진 문자열을 타이핑하기로 했다. 민겸이가 사용할 수 있는 버튼은 26개의 영어 알파벳 버튼과 마름모(◆) 버튼, 별(★) 버튼이다. 각 버튼은 아래와 같이 www.acmicpc.net 문제 설명 접근 방법 먼저, 여태까지 나온 수 중 가장 작은수가 무엇인지를 구한다. 이를 위해서는 입력과 동시에 여태까지 나온 수 중에 가장 작은 수와 입력된 값을 비교하면 된다. 그 후에는 (현재 값- 가장 작은 값)이 여지껏 나온 결과 값 중에 가장 크다면 그 값을, 아니라면 이전의 나온 결과 값을 출력하면 된다. 코드 #include #include using namespace std; int.. 이전 1 다음
