문제 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 현재 위치가 1인 경우 자신의 왼쪽, 왼쪽 위의 대각선, 위쪽을 확인하고 최소 값을 현재 값과 더한다. 그 후 max값을 계속 저장한 뒤 제곱한 값을 출력한다. 1의 위치에서 정사각형의 크기를 계속 계산하는 경우는 DP를 수행하는 것보다 높은 복잡도를 가질 것이다. 제출 코드 # 2023/01/25 DP # https://www.acmicpc.net/problem/1915 import sys input = sys.stdin.readline N, M = ma..
문제 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 현재 위치와 다음 위치를 비교하여 계산하는 문제이다. 처음 풀이는 비용을 pop으로 가져오고, 만약 그 비용이 현재 값보다 더 낮은 경우 이동하고 total_dis 값을 초기화해줬다. 다른 풀이를 찾아봤는데, 이동할 때마다 지불 비용을 비교한 후 낮은 값으로 이동하는 단순한 풀이가 있었다. 제출 코드 # 2023/01/25 그리디 # https://www.acmicpc.n..
문제 https://www.acmicpc.net/problem/4659 4659번: 비밀번호 발음하기 좋은 패스워드를 만드는것은 어려운 일이다. 대부분의 사용자들은 buddy처럼 발음하기 좋고 기억하기 쉬운 패스워드를 원하나, 이런 패스워드들은 보안의 문제가 발생한다. 어떤 사이트들은 xvtp www.acmicpc.net 풀이 주어진 문항에 충실하면 되는 문제, 그대로 구현한 뒤 정답을 출력하면 된다. 모음이 들어가는지 확인 e와 o를 제외한 같은 문자가 반복하는지 확인 자음 및 모음의 개수가 3개 이상인지 확인 위 세가지 항목을 확인하고 정답을 출력한다. 제출 코드 # 2023/01/25 문자열 # https://www.acmicpc.net/problem/4659 import sys input = sy..