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

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

풀이 어떤 문자가 암호화 되어 왕에게 도착하는데, 그 과정은 아래와 같다. J : 모든 문자를 왼쪽으로 회전 C : 모든 문자를 오른쪽으로 회전 E : 문자의 절반을 서로 바꿈 (문자 수가 홀수이면 가운데 문자는 냅둔다) A : 문자를 뒤집는다 P : 문자의 내용 중 숫자만 1씩 증가, 9일 경우 0이 된다. M : 문자의 내용 중 숫자만 1씩 감소, 0일 경우 9가 된다. 이러한 암호와 과정을 함수로 미리 만들어두자. 아래 코드는 문자를 전달받아 위의 암호화 과정에 따라 암호화한 문자를 반환하는 함수들이다. 이렇게 암호화된 문자가 왕에게 도착하고, 왕은 암호화된 문자를 다시 복호화해 원본 문자를 확인하고자 한다. J는 C와, P는 M과 반대로, A와 E는 그대로 유지한채 복호화를 진행해주면 된다. 복호..

풀이 단순한 graph 문제이다. 입력을 받으면서 탐색 위치를(I)를 찾아주자. BFS로 풀이했다. 벽(X)이 아닌 경우와, 이미 방문하지 않은 공간을 탐색해주어야 한다. 위의 조건이 성립하고, 도연이가 사람(P)을 만났다면 만난 사람 수를 업데이트 해주자. 만약 만난 사람이 0명이라면 "TT"를 출력해주어야 한다는 점도 유의하자. 소스코드 소스코드 보기 출처 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net

풀이 N개의 중 3개의 MBTI에 대해서 가장 작은 심리적 거리를 구해야 한다. 모든 경우의 수를 전부 탐색하면 N^3 이기에 당연히 시간초과가 발생할 것이다. 때문에 구한 거리가 0인지 확인을 하고, 중간에 loop를 빠져나와야 한다. 비둘기집 원리를 통해 더 줄여보자. MBTI에 대한 심리적 거리의 최선의 경우는 뭘까? bruteforce이지만, 심리적 거리가 0인 경우 더 이상의 탐색이 무의미하기에 중단 해주어 시간초과가 발생하지 않는다. 심리적 거리가 0이라는 조건 이후의 탐색이 무의미하다면, 심리적 거리가 0이 되는 최악의 경우는 무엇일까? 바로 비둘기집 원리에 따른 33명이다. 서로 다른 MBTI를 가진 16명이 2명씩 총 32명 있을 경우 심리적 거리는 0이 될 수 없다. 33명부터 동일한 ..