0과 1의 쉼터

풀이 A/B에 대해 소수점 아래 N번째 수를 출력하는 문제다. 단, 소수점 아래 10^6번째 자리수를 정확히 구할 수 없다. 때문에, N-1번 만큼 한 자리수씩 10배를 하여 구해주었다. 소스코드 마지막 10배수에 대한 몫이 N번째 수와 동일하다. 소스코드 소스코드 보기 출처 1312번: 소수 피제수(분자) A와 제수(분모) B가 있다. 두 수를 나누었을 때, 소숫점 아래 N번째 자리수를 구하려고 한다. 예를 들어, A=3, B=4, N=1이라면, A÷B=0.75 이므로 출력 값은 7이 된다. www.acmicpc.net

풀이 분수로 이루어진 배열에 대해 N번째 배열의 요소를 출력하는 문제다. 문제에서 주어진 것 처럼 배열의 요소들은 아래의 표처럼 분모와 분자가 뒤바뀌는 것을 알 수 있다. 1/1 1/2, 2/1 3/1, 2/2, 1/3 1/4, 2/3, 3/2, 4/1 5/1, 4/2, 3/3, 2/4, 1/5 1/6, 2/5, 3/4, 4/3, 5/2, 6/1 다음과 같은 규칙이 존재한다. 홀/짝 번째 줄에 따라 분자와 분모의 위치가 변한다. 한 줄에 속한 요소의 다음 요소는 분자와 분모가 1씩 증감하는 규칙이 있다. 다음 줄로 넘어갈 때마다 요소의 갯수가 1씩 증가한다. 한 줄이 가지는 요소 개수만큼 N을 감소시키다 보면 N이 몇 번째 줄(depth)인지 알 수 있다. 또한, 감소시킨 N이 줄의 요소보다 작다면, 그..

풀이 입력받은 배열 A를 오름차순으로 정렬(sorted_A)했을 때, 원본 배열의 요소가 정렬된 배열에서 몇 번째에 위치하는지 구하는 문제다. N은 최대 50으로 모든 요소에 대해 배열을 전부 선형탐색해도 O(N^3) 제한시간 내 통과할 수 있다. 동일한 원소에 대해서도 순서는 별도로 부여되므로, 이미 찾은 요소는 범위를 벗어난 수(-1)로 채워넣어 탐색이 되지 않도록 해주자. 소스코드 소스코드 보기 출처 1015번: 수열 정렬 P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주 www.acmicpc.net

풀이 왼쪽(L), 오른쪽(R) 각각 총 X개씩 1 ~ K번의 양말을 가지고 있다. 양말 개수의 제곱보다 양말 색상의 제곱에 대해 양말의 짝을 찾는게 더 빠르기 때문에 양말에 대한 정보를 입력받을 때 각 색상의 개수를 세주자. 이제 왼쪽 1 ~ K번 색상의 양말 중 존재하는 양말에 대해 오른쪽 양말과 짝을 지어준다. 만약 중복되는 양말짝이 있을 수 있기에, 앞서 미리 세주었던 개수만큼 곱한 값을 더해주자. pypy3로 제출했다. 소스코드 소스코드 보기 출처 28282번: 운명 동원이는 왼발 전용 양말을 총 4개 가지고 있으며, 각 양말의 색은 1, 3, 2, 4번 색이다. 동원이는 오른발 전용 양말을 총 4개 가지고 있으며, 각 양말의 색은 3, 1, 1, 5번 색이다. 동원이가 양쪽 발에 www.acmi..

풀이 N개의 수에 대해 N - 1개의 수식을 적용해 모든 경우를 생각해도 크기가 작아 충분하다. 하지만, 연산자 우선순위에 관계없이 왼쪽부터 오른쪽으로 연산을 하면 되기 때문에 중복해 계산하는 부분이 있다. 이 부분에 대한 값을 stack에 저장해 재사용 하는 방법으로 풀이했다. 0 ~ N-1 번의 index에 대한 탐색이 끝났다면, 최댓값과 최솟값을 갱신해주고, 그렇지 않은 경우에는 아직 사용할 수 있는 연산자에 대해 계산을 해주자. 소스코드 소스코드 보기 출처 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의..

풀이 입력받은 정수 n의 배수 중 1로만 이루어진 배수를 찾아 자릿수를 출력하면 되는 문제다. 간단하게 1부터 시작해서 n으로 나누어 떨어질때까지 숫자 뒤에 1씩 붙여주면 된다. 뒤에 숫자 1을 붙일 때 마다 자릿수를 한 개씩 증가시켜 주자. 소스코드 소스코드 보기 출처 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 각 자릿수가 모두 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net

풀이 기본적인 하노이탑 문제다. 하노이 탑은 3개의 기둥과 N개의 원판에 대해 아래와 같은 조건을 만족할 떄 움직여 마지막 기둥으로 피라미드꼴로 모든 원판을 움직이는 문제다. 조건은 아래와 같다. 한 번에 한 개의 원판만 움직일 수 있다. 가장 위에 있는 원판만 움직일 수 있다. 원판을 놓을 때는 자신보다 큰 원판의 위에만 놓을 수 있다.(어떠한 원판도 없다면 바로 놓을 수 있다) N개의 원판에 대해 i번째로 작은 원판이 A, B, C 기둥으로 움직이는 과정을 생각해보자 N = 1일 때 원판이 한 개 이므로 (3)번 조건에 따라 바로 C 기둥으로 놓을 수 있다. 움직인 횟수는 1회이고, 경로는 A >> C이다 N = 2일 때 1번째로 작은 원판을 B기둥으로 옮겨주자 A기둥에 있는 2번째로 작은 원판은 (..

풀이 새로운 사람이 오픈 채팅방에 입장하면 "ENTER" 이라는 문자열이 입력된다. 그 이후로 곰곰티콘을 사용한 사람이 총 몇명인지를 구하면 되는 문제이다. 즉, 새로운 사람이 들어온 후 곰곰티콘을 사용한 사람의 수를 구하면 된다. 일반적으로 채팅한 모든 사람들에 대해 몇 번 채팅했는지 살펴보는 방법은 O(N^2), N이 100,000이기에 시간초과가 발생할 것이다. 따라서 O(1) 만에 이미 채팅이력이 있는지 확인을 해주어야 한다. map과, set을 사용한 풀이들을 소개한다. HashMap 먼저 이름을 저장할 HashMap으로 nameList를 선언해주자. 누가 몇 번을 채팅했든 상관없이, 1번이라도 채팅했다면 곰곰티콘을 사용한 채팅이 아닌 평범한 채팅 기록이기 때문에 횟수를 계산할 필요가 없다. 때..