7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 최종 코드 import sys input = sys.stdin.readline t = int(input()) ans = list() for i in range(t): n, m = map(int, input().split()) a = sorted(list(map(int, input().split())), key= lambda x:-x) b = sorted(list(map(int, input().split())))..
분류 전체보기
문제 분석 문제를 보면, 입력의 값이 엄청나게 큰 것을 확인할 수 있다. BruteForce를 사용하는 것은 불가능해 보이며, '정해진 총액 이하에서 가능한 한 최대의 총 예산'와 같은 말에서 이분 탐색의 향기가 솔솔난다. 상한액을 mid로 설정하여, 총예산 보다 큰 경우는 max 값을 mid - 1로 설정하여 상한액을 낮춘다. 총예산 보다 같거나 작은 경우는 min 값을 mid + 1로 설정하여 상한액을 높인다. 우리가 구해야 할 값은 max 값이므로 while 문이 끝나는 경우(min > max), max 값이 아닌 min 값이 움직이게 만든다. 남은 알고리즘은 일반적인 이분 탐색과 동일하게 구현하면 된다. 문제 풀이 import java.util.Scanner; public class Main { ..
https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은..
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고..
https://www.acmicpc.net/problem/2999 문제 매일 밤, 정인이는 상근이에게 이메일을 보낸다. 정인이는 자신의 이메일이 해킹당할 수도 있다는 생각에, 내용을 항상 암호화해서 보낸다. 정인이가 사용하는 암호 알고리즘은 다음과 같다. 정인이가 보내는 메시지는 총 N글자이다. 먼저, 정인이는 R
문제 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다. 하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다. 꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다. 꽃을 심을 때는 주의할 점이있다. 어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다. 또 화단 밖으로 꽃잎이 나가게 된다..
문제 이진수 덧셈은 매우 간단하고, 십진수 덧셈과 비슷하게 하면 된다. 십진수 덧셈을 할 때는, 오른쪽부터 왼쪽으로 차례대로 숫자 하나씩 더하면 된다. 이진수 덧셈도 이와 비슷하게 하면 된다. 십진수 덧셈은 외워야 할 덧셈이 많지만, 이진수 덧셈은 아래와 같이 5가지만 기억하면 된다. 0 + 0 = 0 1 + 0 = 1 0 + 1 = 1 1 + 1 = 10 1 + 1 + 1 = 11 두 이진수가 주어졌을 때, 그 합을 이진수로 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 수 T(1
수학적 관찰이 필요한 문제 문제는 진짜 잘 만들었지만 증명하는 데 꽤 오래 걸렸다 코테에서 이렇게 나오면 시간 내에는 못 풀 거 같다. 완전 탐색 매 요청마다 리그전의 재미를 계산한다. Q = 200,000, N = 100,1000, l = 1, r = 100,000 인 경우 200,000 * N!로 시간 초과가 발생한다 완전 탐색 최적화 각 후보 디비전을 계산할 때, 공통적으로 계산되는 부분이 있을 것이다 이를 알기 위해 1번 팀부터 N 번 팀까지 리그전을 진행할 때 생기는 재미에 대한 식을 나열해 본 결과 공통되는 식이 있단 것을 알 수 있다. 아래 표는 예제 1을 풀어쓴 결과다. 표를 보면 1 ~ 3 팀까지 리그전을 할 경우 계산 결과에, 1 ~ 2팀끼리 리그전을 한 계산들이 포함된 것을 알 수 있..
문제 https://www.acmicpc.net/problem/2947 2947번: 나무 조각 첫째 줄에 조각에 쓰여 있는 수가 순서대로 주어진다. 숫자는 1보다 크거나 같고, 5보다 작거나 같으며, 중복되지 않는다. 처음 순서는 1, 2, 3, 4, 5가 아니다. www.acmicpc.net 코드 풀이 배열하는 순서에 따라 적어도 하나가 1,2,3,4,5의 순서가 아니면 배열의 순서를 바꾸도록 실행되어야 하므로 || 연산자를 사용한다. 두 조각의 순서가 바뀔 때 마다 출력해야하므로 바꿔준 조건문 안에서 출력까지 한 이후 돌아가도록 넣어준다.
문제 https://www.acmicpc.net/problem/2789 2789번: 유학 금지 아주 멀리 떨어져 있는 작은 나라가 있다. 이 나라에서 가장 공부를 잘하는 학생들은 모두 다른 나라로 유학을 간다. 정부는 최고의 학생들이 자꾸 유학을 가는 이유를 찾으려고 했다. 하지만, www.acmicpc.net 코드 풀이 입력받은 arr과 CAMBRIDGE를 입력한 univ배열을 이중포문을 이용하여 arr[i]당 univ와 같은 알파벳이 있는지 검사한다. flag로 표시하여 만약 같은 알파벳이 있으면 '?'로 표시하고, 다시 arr을 돌려서 표시한 곳이 아니면 출력한다.
10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 문제코드
https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 문제분석 A와 B로만 이루어진 문자열이 입력으로 주어진다. 입력으로 주어진 문자열이 1. A는 A끼리, B는 B끼리 선으로이어졌을 때, 선이 겹치면 안된다. 2. 문자하나는 문자 하나에만 선을 이을 수 있다. 위 조건을 만족하는 문자열이 몇개인지를 출력한다. 문제풀이 문자끼리 이어지는 경우는, 바로 직전에 같은 문자가 나타났을 때 이므로 스택을 이용하여 풀수 있다. 문자열의 문자를 하나씩 스택에 push하면..
