![]()
https://www.acmicpc.net/problem/11660DP를 이용해 푼 문제이다. 2차원 배열 arr은 문제에서 주어진 입력으로 만든 2차원 배열이고 배열 dp는 행별로 누적합을 구한 배열로 설정한다.그런다음, 행별로 누적합을 구한다. (dp[3][4]는 arr [3][1]부터 arr [3][4]까지 더한 것) import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringT..
![]()
https://www.acmicpc.net/problem/2630알고리즘 분류분할정복, 재귀input = __import__('sys').stdin.readlineN = int(input())Paper = [list(map(int, input().split())) for _ in range(N)]W_cnt, B_cnt = 0, 0def Paper_div(x, y, N): global W_cnt, B_cnt WB_cnt = 0 for i in range(x, x + N): for j in range(y, y + N): if Paper[i][j]: WB_cnt += 1 if not WB_cnt: W_cnt += 1 ..
![]()
https://www.acmicpc.net/problem/4949문제 풀이1. while문을 사용하여 '.' 이 나올 때까지 입력받기2. 한 문장 안에서 ( 나 [ 가 나올 경우 스택에 추가하기3. ) 나 ] 가 나올 경우3-1. 스택이 비어있지 않은 경우- 괄호가 ) 와 ( / ] 와 [ 라면 (짝이 맞다면) 스택에서 pop()하여 요소 제거- 맞지 않다면 제대로 되어있지 않는 괄호 상태 -> flag = False, break로 탈출3-2. 스택이 비어있는 경우- 닫혀있는 괄호 앞에 짝이 맞는 요소가 없음을 의미 -> flag = False, break로 탈출4. 위 조건에서 정상적으로 수행되고(flag가 True) 이고 스택이 비어있다면(괄호들이 전부 짝에 맞게 제거) yes 출력그렇지 않다..
https://www.acmicpc.net/problem/2110문제도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.입력첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주..
![]()
19637번: IF문 좀 대신 써줘 (acmicpc.net)단순 구현 -> 시간 초과이진 탐색 코드로 제출 -> 시간 초과뭐가 문젠가 했더니 입력받는 코드를 바꿔줬더니 통과됨# 반복문으로 여러 번 입력받을 시 input() 대신 sys,stdin.readline()을 꼭 쓰자# 각 캐릭터의 칭호를 찾을 때 이진 탐색import sysinput = sys.stdin.readlinen,m=map(int,input().split())level = []for _ in range(n): a, b = list(input().split()) level.append((a, int(b)))def ubound(x): left = 0 right = n-1 while left
![]()
문제 & 링크https://www.acmicpc.net/problem/1002 풀이1. x1, y1을 중심으로 하고 반지름이 r1인 원과 x2, y2를 중심으로 하고 반지름이 r2인 원의 접점을 구하는 문제이다.2. 두 원의 중심 좌표가 같을 경우 반지름의 길이가 같다면 접점은 무한대가 되고, 다르다면 접점은 없게 된다.3. 두 원의 중심 좌표가 다를 경우 접점이 두 개, 한 개, 없는 경우로 나뉜다.3-1. 접점이 두 개인 경우는 중심 좌표 간의 거리가 각 원의 반지름의 합보다는 짧고, 반지름의 차보다는 긴 경우이다.3-2. 접점이 한 개인 경우는 중심 좌표 간의 거리가 각 원의 반지름의 합과 같거나 반지름의 차와 같은 경우이다.3-3. 접점이 없는 경우는 그 외의 경우이다. 참고 자료빨간색 선: r1..
![]()
문제 & 링크https://www.acmicpc.net/problem/17608 풀이1. 보는 방향, 즉 제일 오른쪽 막대기를 시작으로 잡는다.2. 오른쪽에서 왼쪽으로 막대기를 탐색하며 지금까지 탐색한 막대기 중 가장 큰 것과 비교한다. (max값 구하는 알고리즘과 유사)3. 더 큰 막대기가 있을 경우 count 변수를 증가시키고 가장 큰 막대기를 업데이트한다.4. 2 - 3의 과정을 제일 왼쪽 막대기를 탐색할 때 까지 반복하고 최종 count를 출력한다. 코드#include #include using namespace std;int main() { int N, h; cin >> N; vector high(N); for (int i = 0; i > h; ..
![]()
https://www.acmicpc.net/problem/13410문제문제풀이거꾸로 구구단은 구구단의 결과를 뒤에서부터 읽으며 된다. 예를 들어8*1 = 8 -> 88*2 = 16 -> 618*3 = 24 -> 42반복문을 통해서 N과 1부터 K까지의 수를 곱한 각각의 결과들을 문자열로 만들어서 거꾸로 출력한 후 그 값을 숫자로 변환하여 numbers리스트에 저장한다. sorted() 함수를 통하여 numbers리스트의 원소들을 내림차순으로 정리한 후 가장 큰 원소인 numbers[0]을 출력한다.소스코드N, K = map(int, input().split())numbers = []for i in range(1, K+1): numbers.append(int(str(N*i)[::-1]))number..
![]()
https://www.acmicpc.net/problem/1874문제풀이input = __import__('sys').stdin.readlinen = int(input())x = 1arr = []out = []flag = Truefor _ in range(n): a = int(input()) while 1: if arr and a스택에 1~n의 수를 차례대로 push하면서 중간중간 원하는 수를 pop하여 수열을 만드는 문제-> arr을 stack으로 사용1. n이 커질수록 입력 시행횟수가 증가하기에 표준입력으로 받을 수 있게 함.2. 1~n까지 순서대로 push해야하기에 따로 x라는 변수를 만들어 1씩 증가하며 스택에 추가되도록 함.3. if arr : 로 스택이 비어있는지 확인4..
https://www.acmicpc.net/problem/16401문제명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다.조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다.그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다. 입력첫째 줄에 조카의 수..
![]()
문제https://www.acmicpc.net/problem/27496Algorithm누적합을 이용하여 현재 알코올 농도를 구한다. 이때, 알코올이 지속되는 시간을 고려해야한다. 예제 입력 1을 보면 알코올의 지속시간이 3이므로, 첫번째 술은 3시간까지 적용 후 4번째 시간이후부터는 사라지도록 코드를 구성한다.문제에서 혈중 알코올 농도는 0.001을 곱하여 계산한다고 되어있는데, 이는 부동소수점 문제가 나타난다.해당 사진은 값을 임의로 넣었을때 prefix배열의 출력이다. 우리가 원하는 소수점 3번째 자리까지의 값이 반영이 안되어 있기 때문에, 0.001을 곱하지 않고 정수 그대로 계산한 후에, 해당 시간의 혈중 알코올 농도가 129 ~ 138 사이에 있는지 확인하는 방식으로 바꾸었다. Codeinput..
![]()
https://www.acmicpc.net/problem/10773문제풀이드디어 문제에 자료구조를 적용합니다. 화이팅..총 반복할 횟수를 알기위해 정수 K를 입력받고, stack이라는 변수명의 빈 리스트를 만듭니다.K번 반복할 동안 정수 a를 입력받습니다. 이 때 a는 문제에 기술된 재민이가 기입하는 수이며, 잘못된 숫자를 기입할 때 마다 재현이는 0을 입력받기도 합니다. stack이 비어 있으면 각줄의 a를 stack에 집어 넣습니다.단, a에 숫자 0을 입력받을 시엔 스택의 pop연산이 실행되어 마지막에 입력된 a가 삭제됩니다.0이 아니라면 다시 a를 stack에 집어 넣습니다.K번 반복이 완료되면 stack내에 있는 요소를 모두 더한 값을 출력하고 실행을 종료합니다.문제코드K=int(input())..
