농부공학자

https://www.acmicpc.net/problem/1918 스택 사용하는 문제이다. 처음에는 괄호를 치고 계산하려고 했는데 괄호 치는 과정이 너무 어려워서 관둠. 일단 '(' 가 나오면 ')' 가 나와야하는게 자명함 그리고 ')'가 나오면 '('가 나올 때까지 어딘가에 저장해둔 연산자를 빼야하는것도 자명하다! 그럼 이걸 1. 어딘가에 저장해야하고 2. 연산자를 어떻게 빼서 가져올지 고민하면 될 것 같다. 물론 저도 틀렸음ㅎㅎㅋㅋㅋ 코드 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new Buffered..

https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 오랜만에 푸는 알고리즘......ㅎㅎ map에는 다양한 메소드가 많은데 맨날 put get contains 이런거만 쓰는 것 같아서 언제한번 정리해보려고 한다. 아무튼 풀이를 해보자면 사실 신경써야하는건 얘네가 정렬되는 순서이다. 자주 나오는 단어일수록 앞에 배치한다. 해당 단어의 길이가 길수록 앞에 배치한다. 알파벳 사전 순으로..

https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 생각보다 되게 어려움;;;; 왜냐? 무한루프 엄청 돌았다.ㅋㅋㅋㅋ 10x10이고 색종이도 1x1, 2x2, 3x3, 4x4, 5x5밖에 없어서 완탐이구나 했음 조금 생각해보면 무작정 큰걸 붙인다고 최선인건 아니라는걸 알 수 있다. 그래서 만약에 맵에서 1을 만났을 때 1x1, 2x2, 3x3, 4x4, 5x5 중에 하나를 붙일 테니까 각자 붙일 수 있는지 확인하고 붙이는 방식으로 백트래킹..

https://www.acmicpc.net/problem/8958 8958번: OX퀴즈 "OOXXOXXOOO"와 같은 OX퀴즈의 결과가 있다. O는 문제를 맞은 것이고, X는 문제를 틀린 것이다. 문제를 맞은 경우 그 문제의 점수는 그 문제까지 연속된 O의 개수가 된다. 예를 들어, 10번 문제의 점수 www.acmicpc.net 구현 문제 조지기 해야지 T = int(input()) for _ in range(T): input_ = list(input()) answer = 0 index = 1 O_list = [] for i in input_: stack = [] stack.append(i) if(stack[-1] == 'O'): answer += index index += 1 else: index =..

https://www.acmicpc.net/problem/10162 10162번: 전자레인지 3개의 시간조절용 버튼 A B C가 달린 전자레인지가 있다. 각 버튼마다 일정한 시간이 지정되어 있어 해당 버튼을 한번 누를 때마다 그 시간이 동작시간에 더해진다. 버튼 A, B, C에 지정된 시간은 www.acmicpc.net 위의 문제는 전에 풀었던 거스름돈과 비슷한 문제이다. 좀 더 깔끔하게 짜보려고 했는데 조건이 몇 번씩 누르는지 각자 출력이고, 나누어지지 않으면 -1 출력이기 때문에 또다시 노가다로 표현했다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class B..

https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net A[0] x B[0] + A[1] x B[1] + ... A[N-1] x B[N-1] 의 값이 최소값이 되기 위해서는 A의 가장 작은 수 x B의 가장 큰 수 이런식으로 곱셈이 되어야 한다. 문제에서 A의 배열속 값만 움직일 수 있다고 했지만 B도 같이 움직여줘도 된다. 왜냐면 큰거 x 작은거가 되는 계산값..은 같으니까.... 순서가 중요하지 않으므로 A는 오름차순, B는 내림차순으로 정..

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 내가 푼 방법은 기름값이 싸면 만땅 충전해서 가는게 좋음 그래서 이전 기름값과 비교해서 작은곳에서 다음다음 갈 것 까지 만땅 충전해서 가는것이다... 그러니까 기름값 싼 곳을 찜해놓고 다음 기름값, 다다음 기름값, 다다다음 ... 이렇게 비교해서 작은곳에서 만땅 넣는다. 코드 import java.io.BufferedReader; import java.io.IOException; i..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net https://st-lab.tistory.com/243 엄청난 블로그 설명...!! 풀이도 저 블로그에 아주 잘 설명되어있다.~ 알고리즘을 떠올리지 못했다. 이런 문제를 풀 때는 그려보는게 짱이다! 라는걸 다시 느낌......~ 다음부터는 꼭! 그려보도록 하자.. 2주정도 어학성적때매 쉬었더니 감 더 떨어짐 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arr..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 푸는 방법은 최소값으로 괄호를 만들기 위해서는 - 뒤의 +가 있는 숫자들까지만 괄호를 쳐주면 된다. 무슨 말이냐면... 예를 들어 1+2-3+4+5-10+5 = 2 인데 2- 뒤의 3+4+5를 묶고 - 뒤에 10+5를 묶는다는 것이다. 그래서 1+2-(3+4+5) -(10+5) = -24 라는 값이 나온다. 푸는 방법은 바로 떠올렸는데... string으로 받아올 저 케이스를 어떻게 숫자와 ..

ATM 얘도 그리디 알고리즘 문제 유형에 있는 문제이다. https://ticssfm.tistory.com/32?category=1008893 [Algorithm] 탐욕(그리디) 알고리즘 (greedy algorithm) 그리디 알고리즘은 문제를 해결하는 과정에서 가장 좋다고 생각하는 방법을 선택하는 알고리즘이다. 예를 들어 노드 값의 최대 합은 5 -> 7 -> 9를 거쳐 21임을 알 수 있다. 그러나 그리디 알고리즘 ticssfm.tistory.com 문제를 표로 만들어서 살펴보자 예시에서는 P1 = 3, P2 = 1 ... 이런식으로 5가지 수를 받았다. 이 줄을 오름차순 정렬 한 후 계산을 수행하는 것이 가장 효율적이라고 나타낸다. 그러므로 입력을 받은 후 오름차순 정렬을 하고 계산을 수행해야 하..