IT Crowd

이 문제는 N(2 ≤ N ≤ 1,000,000)이라는 것을 생각하고 풀어야 하는 문제이다. 문제를 해결하려고 가장 첫번째로 생각나는 방법은 아마도 현시점에서 매수를 하고 현재 시점에서 부터 끝까지 탐색해서 그중 최고값을 찾아 이익을 얻는 것일 것이다. 하지만 이방법으로 문제를 풀려고 한다면, 2중 for문이 필요하고 N^2의 시간복잡도를 가지게 된다. 주어진 테스트 케이스를 해결하더라도 N이 커질 경우 시간초과가 발생할 수 있다. 이때, 뒤에서 부터 순회하는 방법을 사용하면 위의 문제를 해결할 수 있다. 뒤에서 부터 순회를 하면서 현시점 (현위치)에서 부터 끝까지 중 최고치를 알아낼 수 있고, 현시점의 매매가 보다 최고 값이 높으면 매수하고 최고치에 팔면 이득을 얻어 낼 수 있다. 설명한 내용을 간단히 ..

www.acmicpc.net/problem/2527 2527번: 직사각형 4개의 줄로 이루어져 있다. 각 줄에는 8개의 정수가 하나의 공백을 두고 나타나는데, 첫 4개의 정수는 첫 번째 직사각형을, 나머지 4개의 정수는 두 번째 직사각형을 각각 나타낸다. 단 입력 직 www.acmicpc.net www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1829&sca=9010&stx=%EC%A7%81%EC%82%AC%EA%B0%81%ED%98%95 JUNGOL www.jungol.co.kr 문제 풀이 이 문제는 가능한 경우의 수를 줄여나가면서 원하는 답을 찾아나가는 방법으로 보다 쉽게 해결할 수 있음 입력에서 사각형1(x1,y1,p1,q1)을 기준으로 하고 사각형2(x..

www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m^2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1≤K≤20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나� www.acmicpc.net 입력 변의 방향이 동,서(1,2)일 경우 가로변, 변의 방향이 남,북(3,4)일 경우 세로변임을 알 수 있음. 6각형이고 입력이 순서대로 들어오므로 변의 방향과 길이를 저장하기 위한 2차원 배열을 생성하여 저장함. 문제 풀이 ㄱ자 모양이라는 것에서 아이디어를 얻음 그림과 같이 큰 사각형에서 작은 사각형을 빼면 ㄱ자 도형의 면적을 구할 수 있음 큰 사각형의 면적 주어진 변의 길이중 가장 긴 가로 변, 세로변의 길..

문제 링크 https://www.acmicpc.net/problem/2628 문제 풀이 세로로 잘리는 위치,가로로 잘리는 위치를 저장하기 위한 리스트 생성하고 0 넣어두기 (시작점) 가로인지 세로인지에 따라서 각각 세로리스트, 가로리스트에 저장 마지막 점 추가( 종이의 가로, 세로크기) 가로, 세로 리스트 정렬 가로/세로 리스트의 두점 (첫번째-두번째, 두번째 - 세번째,…)의 거리 구함 그 중에서 최대값을 구하고 각각 곱하면 정답! 소스 코드 (python) C,R = map(int,input().split()) #세로, 가로 크기 N = int(input()) #자르는 횟수 Rarr = [0] #세로로 잘리는 위치 저장 Carr = [0] #가로로 잘리는 위치 저장 for i in range(N): ..