phanre의 tistory

https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 골드4 주제에 시간초과 최적화 때문에 매우 매우 골치아팠던 문제. Pypy3으로 컴파일 해야한다. 우선 오답 풀이로는 봄을 처리할 때 tree를 3중배열 처리 하지 않고 tree[index]에 age, y, x를 저장하여 모든 tree 탐색을 하며 원소를 pop하고 잠시 temp 배열에 저장한 후 봄 처리가 끝나면 다시 tree에 저장했다. 이렇게 하면 pop과 append를 원소..

https://www.acmicpc.net/problem/3709 3709번: 레이저빔은 어디로 레이저박스라는 게임은 정사각형 모양의 n x n 보드에서 진행한다. (체스판을 상상하면 된다) 레이저박스의 임의의 칸마다 우향우 거울이라는 장치가 설치되어 있고, 마지막으로 레이저 한개가 www.acmicpc.net vector를 설정하여 이동하며 우향우 거울이 있는 경우 vector를 변경하여 탈출할 때 까지 시뮬레이션 하는 문제이다. mirror라는 n*n 배열을 생성한 후 우향우 거울이 있는 위치를 저장해준다. 이후 zero index를 위한 값 변경을 한 후 dy, dx 배열을 상, 우, 하, 좌 순서로 배치한다. 그리고 시작점 위치를 토대로 방향을 설정한 후 거울이 있는지 체크해가며 이동하면 된다. ..

https://www.acmicpc.net/problem/1025 1025번: 제곱수 찾기 첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지 www.acmicpc.net 등차수열의 공차를 설정해 완전탐색하여 set에 add하고 set에서 제곱수이면 현재 max값과 비교하여 저장하였다. def make(y, x, dy, dx, num): yy = y + dy xx = x + dx if dy == 0 and dx == 0: made.add(num) return if 0

https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 두 건물의 기울기를 이용해 두 건물 사이 선분에 건물이 있는지 확인하면 된다. def watch(index): answer = 0 height = build[index] for i in range(n): dx = i - index dy = height - build[i] if dx != 0: d = dy/abs(dx) k = 1 if dx > 0: k = -1 b = 1 for j in range..

https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net n+1개의 arr 배열을 생성하여 컵라면 개수를 arr[끝나는 시간]에 맞게 저장해준다. 끝나는 시간이 널널한 것은 나중에 처리해도 되기 때문에 끝나는 시간 최대값을 m으로 저장하고 arr m부터 1까지 역순으로 heappush후 heappop하여 최대값을 꺼낸다. 최대값을 꺼낸 후 answer를 증가시킨다. import sys from heapq import heappop, heappush input =..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net ArrayList에 관계를 저장 후DFS를 통해 탐색하며 리프노드인지 확인하는데 delete된 노드인지 확인하는 프로세스를 추가한다. 리프노드일 경우 전역변수 count를 증가시킨다. import java.util.*; public class Main { static int count = 0; static int n, del; static int start; static ArrayList[]..

https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net check 함수를 생성하여 내림차순 정렬된 box함수를 탐색 만약 crain[i]가 box의 최소값보다 적으면 crain 이후 값 모두 del 처리 box를 모두 탐색하기 전에 crain이 모두 del되면 -1 return 모두 탐색한다면 반복 횟수 answer return def check(): answer = 0 while box: for c in crain: k = 0 whi..

https://www.acmicpc.net/problem/8972 8972번: 미친 아두이노 요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net 시간초과를 고치기 위해 여러가지 시도했더니 코드가 더러워서 주석으로만 설명. 나중에 리팩토링을 한번 해야겠다. import sys input = sys.stdin.readline def crazy(q): nq = [] same = [] nm = [['.' for _ in range(n)] for _ in range(m)] for ry, rx in q: # 로봇 이동 v = [y-ry, x-rx]..

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 그리디 알고리즘 문제이다 배열로 받아 큰 순서대로 sort후 1번째부터 n번째까지 반복하며 현재 로프보다 굵기 이상인 로프의 갯수 * 현재 로프의 크기를 비교하여 최대값을 print한다 n = int(input()) arr = sorted([int(input()) for _ in range(n)],reverse=True) answer = 0 for i in range(n): answer ..

https://www.acmicpc.net/problem/25046 25046번: 사각형 게임 (Small) 이 문제는 풀이 방식에 따라 Python3를 이용하여 풀 수 있음이 보장되지 않습니다. Python3를 이용하는 분들은 Python3과 같은 문법을 가지면서 일반적으로 더 빠르게 동작하는 PyPy3를 이용해 제출하 www.acmicpc.net 브루트포스 방식으로 민우가 고를 수 있는 경우의 수를 모두 실행한다 n이 5일때는 아무것도 고르지 않는 것부터 0,1,2,3,4 모두 고르는 것 까지 모두 탐색한다 이후 종진이는 자신이 가장 이득을 볼 수 있는 경우를 고르기 때문에 col 배열을 만들어 이미 민우가 골랐다면 +, 고르지 않았다면 -를 하여 더해준다 반복한 후 sort하여 0 이상인 최대값들을..