![]()
수학적 관찰이 필요한 문제 문제는 진짜 잘 만들었지만 증명하는 데 꽤 오래 걸렸다 코테에서 이렇게 나오면 시간 내에는 못 풀 거 같다. 완전 탐색 매 요청마다 리그전의 재미를 계산한다. 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하면..
![]()
1874번: 스택 수열 (acmicpc.net) 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 코드 import sys input=sys.stdin.readline n = int(input()) p = [] # 입력 받은 수열 q = [] # 스택 s = [] # '+' or '-' ans = [] # p와 일치 유무 확인 r = 1 for _ in range(n): num = int(input()) p.append(nu..
![]()
https://www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 문제 소스코드 문제풀이 대소문자 상관없이 가장 많이 사용된 알파벳을 구하는 문제기 때문에 문자열을 입력받고 모두 대문자로 변환해주었다. set을 이용하여 중복을 제거하였고, 그 후 원소를 하나씩 뽑아서 문자 개수를 비교하였다.
문제 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net Algorithm 우선 리스트 A에 입력값을 넣고 정렬한다. 정렬된 값이므로 숫자가 바뀌면 이전 숫자는 다시 나타나지 않는다. A의 마지막 요소부터 시작하여 현재의 숫자 a를 다른 리스트 N에 추가하고 어떤 숫자의 빈도수를 기록하는 리스트 F에 1을 추가한다. A의 다음 숫자 b가 이전에 나타난 숫자 a와 같으면 F에 저장되어 있는 마지막 수에 1을 더하고 그렇지 않으면 F에 1을 추가하고 N에 b를 추가한다. 이 때 b가 a와 다를 경우가 발생하면 a..
![]()
14561번: 회문 (acmicpc.net) 14561번: 회문 n진수는 base가 n인 수를 말한다. 예를 들어 십진수는 base가 10인 수이다. n진수의 수 AmAm-1Am-2…A1A0를 n진수로 표현해보면 AmAm-1Am-2…A1A0 = Am × nm + Am-1 × nm–1 + Am-2 × nm–2 + … + A1 × n1 + A0 × n0이다. www.acmicpc.net 십진수 a가 n진수로 변환했을때의 값이 회문인지 아닌지를 판별하는 문제이다. 먼저 십진수 a를 n진수로 변환해야하므로, 빈리스트와 while문을 설정하여 append 해주었다. 변환한 값이 회문인지 아닌지를 판별해야하므로 for문을 이용하여 한번이라도 회문이 아닌 상황이 오면 flag = False로 설정하였다. 변환값이 회..
https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net import java.util.Scanner; public class Main { public static int[] stack; public static int size = 0; public static void main(String[] args) { Scanner in = new Scanner(System.in); StringBuilder sb = new StringBuild..
![]()
https://www.acmicpc.net/problem/14561 14561번: 회문 n진수는 base가 n인 수를 말한다. 예를 들어 십진수는 base가 10인 수이다. n진수의 수 AmAm-1Am-2…A1A0를 n진수로 표현해보면 AmAm-1Am-2…A1A0 = Am × nm + Am-1 × nm–1 + Am-2 × nm–2 + … + A1 × n1 + A0 × n0이다. www.acmicpc.net 와 진짜 3일동안 고민하고 여러곳에 질문드렸는데 어이없게 틀렸다고 떴던문제 while문 break를 안했습니다 ㅋㅋㅋㅋㅋㅋㅋㅋ..... 예제는 맞게 출력되는데 환장하는줄 알았습니다 앞으로도 화이팅
문제 분석 완전탐색으로 풀기에는 M의 크기와 N의 크기를 곱했을 때 21억을 넘어감으로 불가능하다. 따라서 시간을 최적화해야 되는데, 이분탐색을 적용했다. 절단기의 높이가 0부터 주어진 나무의 최대값까지 선형적으로 있다고 가정하고, 절단기의 높이를 이분탐색을 통해 찾는다. 중간점검을 진행할 때, 절단된 높이의 합과 M의 길이를 비교하여 다음과 같이 min값과 max 값을 변경한다. 절단된 높이의 합이 M보다 크거나 같은 경우: min 값을 mid + 1로 갱신 절단된 높이의 합이 M보다 작은 경우: max 값을 mid - 1로 갱신 주의할 점은 절단된 높이의 합은 int를 초과할 수 있으므로 long으로 선언해줘야 한다. 문제 풀이 import java.util.Scanner; public class M..
