소프티어

동계테스트 런타임오류

동계테스트 3,4 6,7 10,11 런타임 오류가 나는데 ㅜㅜ 어디서 틀린건지 잘 안보이네요 ㅜㅜ import sys # 입력부. N, M = map(int,sys.stdin.readline().split()) mat = [] for i in range(N): tmp = list(map(int,sys.stdin.readline().split())) mat.append(tmp) AIR = 0 ICE = 1 VISIT = 2 def dfs(x,y): # 범위를 나가는 경우 return if x<0 or x>=N or y<0 or y>=M: return 0 # 공기를 만나면 VISIT으로 바꿈 if (mat[x][y] == AIR): mat[x][y] = VISIT #visited, 외부공기 return 1 + dfs(x-1,y) + dfs(x,y...

우물 안 개구리 런타임 에러 ㅠ

예제 테스트케이스랑 제가 만든 테스트 케이스는 잘돌아가는데 채점 하면 런타임에러가 반 이상 나네요...ㅠㅠㅠ 어디가 잘못된건까요.. #include #include int main(void) { unsigned int n,m; scanf("%d %d", &n, &m); long long int w[n]; for(int i =0 ; i

지우는 소수를 좋아해 예외 케이스 좀 받을 수 있을까요?

다익스트라를 이용한 풀이가 정해라는 것은 알고 있습니다만 parametric search + bfs 로도 해결이 가능할 것 같아서 시도해 보았는데 5~6개의 케이스가 자꾸 통과가 안되네요.. 예외 케이스 좀 받아볼 수 있을까요? #include #include #include #include using namespace std; #define MAXN 1000000001 queue q; vector> v[10001]; bool bfs(int start, int end, int level) { bool vi[10001]; fill(vi, vi + 10001, false); q.push(start); vi[start] = true; while (!q.empty()) { int now = q.front(); q.pop(); if (now == end) return true; for (int i = 0; i < v[now].size(); i++) { int n...

장애물 인식 프로그램 TC9 런타임 에러 질문

처음 지도를 배열에 초기화한 다음 (r, c) 기준에서 위 아래 좌 우로 재귀적으로 파고드는 형식으로 체크하도록 하였습니다. 나머지 케이스는 모두 통과하였는데 TC9에서 런타임 에러가 발생하는데 이유가 뭔지 모르겠습니다. 제 추측에는 재귀적으로 파고드는 방식이다 보니 호출 스택의 최대 허용치를 벗어난건가 싶긴한데 지도 최대크기인 25에서 몇가지 케이스로 돌려보아도 런타임 에러를 재현할 수가 없었습니다. 고수분들의 조언 부탁드립니다 ㅠ.ㅠ import java.util.*; import java.io.*; public class Main { private static int mapSize; private static int[][] map; public static void main(String args[]) throws IOException { BufferedReader br = new BufferedRead...

금고털이 문제

안녕하세요. 금고털이 문제 질문드립니다. 테스트 케이스를 풀면 2개가 시간초과되어 오답처리가 되는데요. 여러번 시도 해봐도 잘 안풀리더라고요. 인터넷 검색을 해보니 아래와 같은 해답이 공유되어있더라구요. import sys w, n = input().split() w, n = int(w), int(n) plist = [0 for i in range(n+1)] for i in range(n): mi, pi = input().split() mi, pi = int(mi), int(pi) plist[pi] += mi print(plist) num, total = len(plist)-1, 0 while w>0: if w < plist[num]: total += (w * num) w -= w else: total += num * plist[num] w -= plist[num] num -= 1 print(total) 근데 위 코드의 문제 점 중 하나가 금속의 kg당 가격이 금속의 개수보다 ...

GBC 반례 예시 부탁드립니다.

import sys N_limit, N_test = map(int, input().split()) limit = [] test = [] for i in range(N_limit): limit.append(list(map(int, input().split()))) for i in range(N_test): test.append(list(map(int, input().split()))) k = 0 d_limit = 0 d_test = 0 v_limit = limit[k][1] v_test = 0 Result = 0 for i in range(N_test): d_test = d_test + test[i][0] v_test = test[i][1] if Result < v_test - v_limit: Result = v_test - v_limit if d_test > d_limit: while d_test > d_limit: d_limit = d_limit + limit[k][0] v_...

강의실 배정 python 시간 초과 질문입니다2

이전 질문 링크: Softeer 최소힙을 사용하여 문제를 해결하였습니다. 그런데 1) 한번에 heapify (O(n))진행 후, 하나 씩 heappop(O(nlogn))을 하는 경우(전체 O(nlogn))에는 시간초과가 발생하고 2) 하나 씩 heappush (O(nlogn))진행 후, 하나 씩 heappop(O(nlogn))을 하는 경우(전체 O(nlogn))에는 통과합니다. 일반적으로 힙정렬이 다른 정렬에 비해 일반적으로 느린 편으로 알고 있고, 1)의 경우에도 Tim sort를 진행한 경우보다 느린 것을 확인 할 수 있었습니다. 2)의 경우가 1)과 Tim sort보다 빠르게 진행되는 이유가 궁금합니다. (n의 크기가 충분히 크지 않아 상수 C의 차이가 더 중요한 것일지도 모릅니다. (실제 동작시간: Cnlogn+a)) 추가적으로 1),2), list.sort()(Timsort) 세 가지 풀이 모두 시간 복잡도는 O(nlogn)으로 동일합니다. 문제의 의도가 같은 로직이라...

강의실 배정 python 시간 초과 질문입니다

Python으로 아래와 같이 코드를 작성하였는데, 시간 초과가 발생합니다. 최대 시간이 걸린 케이스 기준으로 입력값(input)을 받아오는데 600ms 정도가 걸렸고, 내장함수 list.sort()를 이용한 정렬을 마치면 총 2090ms 가량이 소요되어 시간 초과가 발생합니다. 알골선생 풀이(링크: Softeer) 역시 같은 로직으로, 종료 시간을 기준으로 정렬 후 강의실을 배정하여 O(nlogn)의 시간복잡도를 가지는데 시간 초과가 왜 발생하는지 모르겠습니다. 1) 내장함수인 list.sort()에서 사용되는 Tim sort는 일반적인 경우에 빠르며 배열이 완전 무작위인 최악의 경우에도 시간복잡도가 O(nlogn)인 것으로 알고 있고 있는데, Python으로 이 문제를 해결할 수 있는 다른 정렬 방법이나 알고리즘이 있는 것인지 궁금합니다. 2) 최대 입력값을 고려해보면 필요 연산이 C*106 *log106 정도로 대략 C *20,000,000(C*2000만) 정도로 예상되는데...

[인증평가(3차) 기출] 교차로 -> 이 문제 관련 질문드립니다.

[인증평가(3차) 기출] 교차로 문제 관련 질문 드립니다. 제약조건에 첫번째가 2 <= N <= 200000 인데, N이 진입하는 차량 대수 라고 생각했습니다. (A, B, C, D에 진입하는 총 차량의 수) 그런데 문제에 진입하는 차량이 1대인 경우가 있었습니다. 제약조건의 N이 어떤것인지 알 수 있을까요? 몇일째 고민하는데 잘 모르겠습니다. 같이 고민해주시면 감사하겠습니다.