0과 1의 쉼터

풀이 스택이란 항아리 처럼 나중에 집어넣은 것이 먼저 나오는 제한적 접근 나열 구조이다. LIFO(Last In First Out) 형식이며, 기본 개념을 구현만하면 된다. 단, 한 줄에 하나씩 출력해야 한다는 것을 명심하자 pop 명령을 실행하기 전에 스택이 비었는지 확인하기 위해 empty 명령어만 함수로 구현했다. 실제 메모리에 대한 참조를 해제할 필요 없이, 변수 top을 사용해 값을 가르키는데 제한을 두었다. 소스코드 소스코드 보기 출처 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net..

풀이 가중치가 없는 방향 그래프가 주어질 때, 모든 정점 간 연결이 가능한지 아닌지를 탐색 후 인접 행렬 형식으로 표현해주면 된다. Floyd Washall 을 사용해서 풀이했다. 가중치는 없지만, 결국 모든 탐색 가능한 정점에 대해 정점 간 연결이 존재하는 경우 또 다른 정점간의 간접적 연결이 되기 때문이다. 단, 단순히 정점간의 간접적 연결에 대한 유무 판단만 하면 되기에 아래의 조건만 충족한지 살펴보자 소스코드 소스코드 보기 출처 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net

풀이 최대 100개의 카드 중에서 3장의 카드를 고를 수 있는 모든 경우의 수를 탐색해도 제한 시간 내 합을 출력할 수 있다. 3개의 카드를 골라야 하니 3중 loop을 사용해 탐색하자. loop의 조건이 순서대로 1씩 감소하는 이유는, 최악의 경우 중복된 카드를 뽑지 않고서는 N - 2 ~ N 번째 카드를 선택했을 때가 조건에 맞는 최댓값이 나오는 경우이기 때문이다. 소스코드 소스코드 보기 출처 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net

풀이 단순히 초코바 구매가 가능한지 아닌지만 판별하면 되기 때문에 100N이 M 이상인지만 알 수 있으면 된다. 소스코드 소스코드 보기 출처

풀이 입력으로 주어진 문자열 S 안에 2N + 1길이의 Pn이 겹침을 허용해서 몇 개 존재하는지 찾으면 되는 문제다. 최대 길이 M에 대한 Pn의 길이는 (100만 - 1) 이기 때문에, 아래처럼 모든 구간에서의 Pn을 구하면 시간초과가 발생한다. N = 2, M = 15, S = IOIOIOIOIOIOIOI 일 때, IOIOI IOIOI IOIOI ... 처럼 매번 2N + 1 길이만큼의 문자열이 주어진 문제의 조건을 만족시키는지 확인하면 시간초과가 발생할 것이다. 때문에, 이미 조건을 만족시키는 문자열을 다시 확인하지 않고 풀이하는 방법이 필요하다. 먼저, 올바른 Pn이 만들어지는 조건을 살펴보자 Pn은 'I' 부터 시작한다. 문자열 S의 M - 1 번째가 'I' 아니면, Pn은 만들어지지 않는다. ..

풀이 처음에 주어진 입력이 모두 0이거나 1일 경우 '0' 또는 '1'이 정답이 되지만, 위의 경우가 아닌 경우 사분면을 'Z' 순서대로 살펴보며 주어진 영역에 대해 모두 하나의 값이 존재할 때까지 recursive call 방식으로 풀이하면 된다. 문제에서 주어진 예제를 살펴보자. 색 (빨 - 주 - 연) 순서대로 분할할 것이며, 색상별 동그라미는 각 분할 시점의 기준 좌표가 된다. 기준좌표에 recursive를 거쳐 줄어든 크기(size)만큼의 영역에 대해 다시 탐색을 시도해 나가며 풀이하면 된다. 참고로 입력의 제한 중 다음과 같은 조건이 있기 때문에 "N은 언제나 2의 제곱수로 주어지며" recursive할 영역을 무조건 2로 나누어 범위를 재설정하면 된다. 소스코드 소스코드 보기 출처 1992번..

풀이 1부터 N까지 각 수의 3제곱으로 이루어진 합을 구하면 된다. 소스코드 소스코드 보기 출처 20833번: Kuber Nadja klistrar ihop små träkuber med sidlängd 1 till större kompakta kuber. Hon har nu bestämt sig för att hon vill ha en kub av varje sidlängd från 1 till N. Hur många småkuber behöver Nadja? www.acmicpc.net

풀이 주어지는 데이터의 개수가 0일 때까지, 데이터 개수의 홀짝 여부에 맞게 데이터들의 중앙값을 출력해주면 된다. 문제에서 구해야 하는 중앙값은 아래의 조건에 따라 구할 수 있다. n이 홀수인 경우, 중앙값은 (n+1)/2의 위치에 있는 데이터이다. n이 짝수인 경우 중앙값은 n/2 와 (n/2)+1 위치에 있는 데이터의 평균값이다. 배열의 인덱스가 0부터 시작한다는 점과 주어진 형식에 맞게 출력해야 한다는 점을 유의해 문제를 풀자. 소스코드 소스코드 보기 출처 9782번: Median ค่ามัธยฐาน หรือ Median คือค่ากึ่งกลางของกลุ่มข้อมูลที่เรียงลําดับ นั่นคือจํานวนข้อมูลที่น้อย www.acmicpc.net

풀이 종류별로 치킨을 최대 N 마리를 살 수 있으며, 종류별로 치킨을 선호하는 인원이 A, B, C이므로 종류별로 최대치와 대소 비교를 통해 알맞은 수량을 출력해주면 된다. 소스코드 소스코드 보기 출처 27110번: 특식 배부 설날을 맞아 부대원들을 위해 특식으로 치킨을 주문했다. 후라이드 치킨, 간장치킨, 양념치킨을 각각 $N$마리씩 주문했고, $1$인당 치킨을 한 마리씩 배부하고자 한다. 최대한 많은 부대원에게 본 www.acmicpc.net

풀이 현재 일요일 날짜 n과 2주 전의 일요일 날짜 m이 주어질 때 1주일 전의 일요일 날짜를 구하면 되는 문제다. n이 충분히 크면(8 이상) n에서 7을 빼고, 충분하지 않으면 m에 7일을 더한 결과가 정답이다. 소스코드 소스코드 보기 출처 27182번: Rain Diary Petya lives in Saint Petersburg and he is keen on meteorology. It is widely believed that it constantly rains in Saint Petersburg. Petya has decided to statistically prove or disprove this statement. For this Petya started a rain diary and ev..