AndroidTeacher

www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루 www.acmicpc.net 문제 설명 다솜이는 기타를 많이 가지고 있다. 그리고 각각의 기타는 모두 다른 시리얼 번호를 가지고 있다. 다솜이는 기타를 빨리 찾아서 빨리 사람들에게 연주해주기 위해서 기타를 시리얼 번호 순서대로 정렬하고자 한다. 모든 시리얼 번호는 알파벳 대문자 (A-Z)와 숫자 (0-9)로 이루어져 있다. 시리얼번호 A가 시리얼번호 B의 앞에 오는 경우는 다음과 같다. A와 B의 길이가 다르면, 짧은 것이 먼저 ..

www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 문제 설명 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 ..

문제 설명 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오. 풀이 과정 소수란 1과 자기자신을 제외한 수로는 나누어 떨어지지 않는 수를 말하는데, 이 소수를 구하는 방법에는 대표적으로 세가지가 있다. ① i를 2부터 n-1까지 돌면서 i로 나누어 떨어지는 경우가 존재하지 않으면 소수 ② i를 2부터 루트n까지 돌면서 i로 나누어 떨어지는 경우가 존재하지 않으면 소수 ③ 에라토스테네스의 체 ①번과 ②번의 경우에는, 명확하게 ②번의 경우의 범위가 더 좁..

www.acmicpc.net/problem/5525 5525번: IOIOI 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000) www.acmicpc.net 문제 설명 N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오. 풀이 과정 문자열 S를 for문을 돌면서 i를 만날 경우 현재 인덱스를 stack에 넣어준다. (예를 들어, ooi..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 설명 이 문제는 아주 평범한 배낭에 관한 문제이다. 흔히, 냅색(Knapsack) 알고리즘이라고 불리는 문제이다. 배낭의 용량이 정해져 있을 때, 최대한의 가치를 가지도록 배낭을 싸야 한다. 주어진 물건들의 용량과 가치를 고려하여 주워담을지 말지 정하는 문제이다. 풀이 과정 먼저, 내 배낭이 버틸 수 있는 용량이 7이라고 하자..

www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 설명 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 풀이 과정 이 문제는 코드는 간단해보일지 몰라도, 아이디어를 떠올리는 과정이 굉장히 까다로웠다. 나는 DP와 순열과조합의 개념을 조합하여 아이디어를 떠올렸다. 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 d[N][K]에 저장한다고 하자. N = 2, K = 1 일 경우 0부터 2까지..

www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 설명 포도주가 ( a, b, c, d, e, f ) 식으로 일렬로 나열되어 있다. a, b, c, d...는 포도주의 용량을 뜻한다. 연속으로 3잔 이상을 마실 수 없을 때, 최대로 마실 수 있는 포도주의 용량을 구하면 된다. 풀이 과정 6잔의 포도주 ( 6, 10, 13, 9, 8, 1 ) 가 있다고 생각해보자. 마지막 포도주를 마실지 말지를 결정하는 상황이라고 할 때, 내가 9와 8을 이미 마셨다면 1은..

www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 설명 자세한 문제 설명은 위의 링크에 나와있습니다! 피보나치 함수란, N번째 수의 값이 N-1 + N-2 의 값이 되는 함수입니다. fibonacci(N) 을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 문제입니다. 풀이 과정 이 문제를 문제에서 주어진 C++코드를 그대로 이용해 0과 1의 횟수를 구하려고 하면 시간초과가 난다. 왜냐하면 f(10)을 호출했다고 가정할 때, f(10) = f(9) + f(8)이 되기 때문에 f(9)와 f(8)을 한번씩 호출하게 되는데, f(9) = f(8)+f..

www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 설명 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 풀이 과정 이 문제는, 전의 결과를 다음 결과에 이용하게 되는. 점화식을 활용한 DP 문제이다. X = 10인 경우, 10 -> 9 -> 3 -> 1 과정을 거쳐 1이 되게 되는데 9의 경우에는 또, 9 -> 3 -> 1의..

www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 설명 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 숫자를 버리는 함수이다. 배열의 ..