0과 1의 쉼터

문제 In St Petersburg phone numbers are formatted as “XXX–XX–XX”, where the first three digits represent index of the Automated Telephone Exchange (ATE). Each ATE has exactly 10 000 unique phone numbers. Peter has just bought a new flat and now he wants to install a telephone line. He thinks that a phone number is lucky if the arithmetic expression represented by that phone number is equal to zero..

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

풀이 N명의 플레이어가 가진 카드에 대해서 서로 다른 플레이어의 카드 간 배수가 존재하는지 판별하는 문제다. 문제에서 두 번 이상 등장하는 카드는 없다고 하니 해당 번호의 카드의 존재여부를 기록해두면 쉽게 풀이할 수 있다. N명의 player에 대해 카드 번호를 입력받고 i번째 플레이어가 가진 카드가 있다고 표시해주자. 그 다음에는 N명의 player가 가진 카드의 배수에 해당하는 카드가 있는지 확인해주면 된다. 만약 카드 숫자가 i 일 때 카드 숫자가 j 인 카드가 있다면, j % i == 0 즉 j는 i의 배수다. 만약 최대 숫자 1,000,000 (SIZE - 1) 에 대해 i 배수를 탐색했는데 만족하는 카드가 없다면, i 카드를 가진 player는 점수를 얻을 수 없다. 점수를 score 배열에 ..

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

풀이 빙고를 풀면 된다. 뭔... 구분을 위해 아래와 같이 표를 만들었다. 우선 조건없이 색칠 가능한 칸을 찾아보자. 이제부턴 추리를 해야한다. C1이 참이라 가정을 해보자. A1, B2, C3, D4, E5가 참이여야 한다. B2에 의해 최소 한개의 세로 빙고줄이 있어야 하지만, B1에 의해 E1은 색칠될 수 없고, D3의 조건에 부합하지 못해 결국 아무런 세로 빙고줄이 만들어지지 않는다. C1이 아니므로 불가능 표시(검정색)를 해주었고, 다음으로 A1이 성립하지 않는경우로 추리해보겠다. E2는 진행에 따라 다르니 일단 C4가 참이라고 가정하고 계속 진행해보겠다. E2와 E3만 성립한다면, B2는 참이다. 일단은 아직까지는 전부 성립한다. 남은 칸들에 대해 진행을 해보자. D3이 성립하는지 살펴보자. ..

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

풀이 다음 일식이 언제 일어나는지 연도를 구하면 되는 문제다. 입력으로는 태양과 달에 대해 몇 년전에 일식이 일어나는지와, 태양과 달이 한 바퀴 공전하는데 얼마나 걸리는 지가 주어진다. 즉, 공전주기는 ys, ym이기 때문에 초기 공전은 ys - ds, ym - dm으로 계산해주어야 한다. 대소비교를 통해 공전주기를 더해주면서 일식이 일어나는(두 연도가 일치하는) 시점까지 반복문을 돌려주자. 입력은 5000년 이내에 일식이 일어나도록 주어지므로 일치 여부만 판단하면 된다. 소스코드 소스코드 보기 출처 27590번: Sun and Moon You recently missed an eclipse and are waiting for the next one! To see any eclipse from your ..

풀이 각 요일마다 주어진 상담을 진행할 경우 겹치는 분기를 표시한 그림이다. 상담 시작요일은 다 다르지만, 상담이 끝나는 날은 다른 상담기간과 겹치는 것을 확인할 수 있다. 때문에, brute force방식(또는 bottom-up)으로 풀이할 경우 모든 상담일정 기간 이후의 모든 기간에 대해 반복문을 돌며 최대 수익을 반영해줘야 한다. 아래 그림처럼 말이다. 좀 더 효율적으로 풀이해보자. 이전 방법은 현재 상담을 통해 미래의 최대 수익이 변화한다는 특징이 있었다. 하지만, 미래에서 현재까지 거꾸로 최대 수익을 계산하는 방법은 어떨까? 미래의 상담일정은 현재의 상담일정에 대해 영향을 끼치지 않는다. 시간은 거꾸로 흐르지 않기 때문이다! 상담 일정이 퇴사 일정을 초과하지 않는다면, 다음 날(day + 1)에..