문제 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 문제 풀이 bfs로 그래프를 탐색하여 그림의 개수와 가장 큰 그림을 찾아내는 문제. 첫 시도에서 Value Error가 발생. input : 1 1 0 이라는 케이스에서 max(cnt_list)에서 에러가 발생하여 예외처리를 했더니 문제 해결. 코드 from collections import deque direction = [(-1, 0), (0, -1), (1, 0), (0, 1)] def bfs(graph, node): queue = deque() queue..
문제 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 틀린 코드 N,M = map(int,input().split()) num_list = [-1]+list(map(int,input().split())) for _ in range(M): start_index,end_index = map(int,input().split()) print(sum(num_list[start_index:end_index+1])) 문제 풀이 처음 이 문제를 단순 구현으로 생각해서 시간초과가 났었습니다. 정수 범위를..
문제 11502번: 세 개의 소수 문제 정수론(수학)에서, 세 개의 소수 문제(3-primes problem) 는 다음과 같은 추측을 말한다. '5보다 큰 임의의 홀수는 정확히 세 개의 소수들의 합으로 나타낼 수 있다. 물론 하나의 소수를 여러 번 더할 www.acmicpc.net 풀이 이 문제는 여러 가지 테스트케이스에서 어떤 수가 주어졌을 때, 세 개의 소수의 합으로 나타낼 수 있는지를 확인하는 문제입니다. 그렇다면 우선 소수를 걸러내는 에라토스테네스의 체가 필요할 것이며, 매 테스트 케이스마다 소수를 새로 구하지 않고 한 번만 계산하는 것이 좋아 보입니다. 소수들을 찾았으면 소수들의 합으로 나타내야 합니다. 이는 세번의 for문으로도 충분히 풀리게 되는데 그 이유는 1000까지의 소수의 개수가 16..
1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 이 문제는 연속된 순열의 합 중 가장 큰 수를 구하는 것입니다. 해당 문제를 접근하기 위해 다음과 같이 가정했습니다. 1. 어떤 한 부분의 연속된 합을 구할 때 앞서 선행된 계산들이 완료되었다. 2. 해당 부분의 가장 긴 연속된 합은 (앞서 선행된 계산 + 현재의 값)과 (현재의 값)을 비교하여 더 큰 값이다. 이 조건들이 만족된다면 가장 큰 연속 합을 구할 수 있습니다. 정답 코드 # 다이나믹 프로그래밍으로 해당 위치까지 도착했을 때의 가장 큰 합을 저장한다. n ..
1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 처음 접근 할 때 N의 크기를 확인하지 않고 순열을 구현하여 해당 순열의 길이만큼을 출력하는 코드로 구현하려 했습니다. 오답코드 # 00과 1의 조합으로 얼마나 많은 경우의 수가 나올 수 있는가 from itertools import permutations N = int(input()) count_00 = N//2 count_1 = N%2 count_possible = 0 for i in range(count_00+1): tmp = list(0 for _ in ran..
간단하게 생각하다 틀린 문제입니다. 2563번: 색종이 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 처음 접근은 단순히 겹치는 구간을 N*100에서 빼면 된다고 생각했습니다. 틀린 코드 #색종이의 크기는 모두 10*10이다 #겹치는 부분을 빼면 될 것. N = int(input()) position_arr = [] for _ in range(N): position_arr.append(list(map(int,input().split()))) # position_arr.sort() # print(position_arr) area =..
