본문 바로가기

백준

 (81)
1057)토너먼트 https://www.acmicpc.net/problem/1057 토너먼트에 참가하는 사람 두 명을 지정해주면 그 두 사람이 몇 라운드에서 만나는가를 찾아야 한다. 시뮬레이션 문제라 토너먼트 상황과 비슷하게 문제를 풀었다. 우선 사람 수만큼 배열을 할당하고 지정된 두 사람의 인덱스에 TARGET을 저장한다. 아래 과정은 토너먼트의 각 라운드에 참여하는 사람들의 수가 홀수이냐 짝수이냐에 따라 차이가 있다. 배열을 순차적으로 두 개씩 비교해 두 개 모두가 TARGET이면 그때 라운드 수를 반환하고 하나만 TARGET일 때 임시 인덱스 위치에 TARGET을 저장하고 임시 인덱스를 하나 증가시킨다. 둘다 TARGET이 아니면 임시 인덱스 위치에 NON_TARGET을 저장하고 임시 인덱스를 하나 증가시킨다. 12..
1094)막대기 https://www.acmicpc.net/problem/1094 알고리즘을 말로 설명해주고 있어 알고리즘을 짜는 것은 어렵지 않다. 64,32,16,8,4,2,1 중 하나 씩 더해서 64 이하의 수들을 표현할 수 있다. 예를들어 23은 16,4,2,1 을 더해서 얻을 수 있다. 위 수들은 2를 0~6번거듭제곱해서 얻을 수 있다는 점을 이용해 len[7]을 선언하고 len[6]에 1을 할당해주면 초기 상태를 만들 수 있다. len[6]=1은 2^6이 하나 있다는 뜻이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include#define..
1748)수 이어 쓰기 1 https://www.acmicpc.net/problem/1748 1~N까지 각 수를 이어 붙여 새로운 수를 만들 수 있을 때 이 수의 길이를 찾는 문제다. 예를들어 N = 12라면 새로 만들어지는 수는 123456789101112 이다. 이 수의 길이를 구하기 전에 각 자리수들의 수를 세어보자. 1~9 : 9개10~99 : 90개100~999 : 900개 이제 N=12일때 새로 만들어진 수의 길이는 1~9까지 9*1개 10~12 까지(12-10+1)*2개이다. N=120이면 9*1+90*2+(120-100+1)*3개이다. 이것을 코드로 그대로 구현하면 된다. 123456789101112131415161718192021222324252627#include int main() { int N; int tem..
5212)지구 온난화 https://www.acmicpc.net/problem/5212 문제를 단순화 해보면 'X'에 인접한 '.'가 3개 이상이면 'X'를 '.'로 바꿔 주는 게 전부이다. 여기서 인접해있다는 말은 대각선 방향이 아닌 네 방향으로 인접한 것을 뜻한다.그림처럼 'X'를 기준으로 상하좌우만 고려했을 때 모두 '.'이기 때문에 X를 '.'으로 바꿔줘야 한다. 다른 문제를 생각해보자. 만약 'X'가 경계나 모서리에 위치해있을 때 어떻게 인접한 '.'를 세어야 할까? 그림에서 표시된 'X'는 모두 배열 경계 바깥 쪽에 '.'이 있는 것으로 간주하고 '.'의 수를 세어야 한다. 왜냐하면 주어진 입력은 최소 크기의 섬이 있는 지도이기 때문이다. 지도 바깥은 모두 바다라고 간주해야 한다.'X'가 배열의 경계에 위치할 때 ..
2810)컵홀더 https://www.acmicpc.net/problem/2810 좌석의 양 끝에 컵홀더가 있고 좌석 사이마다 컵홀더가 하나씩 놓여있다. 좌석은 S와 L 두 가지 종류가 있으며 L은 커플석으로 두 개씩 붙어있고 그 사이에는 컵홀더가 없다. 예시로 좌석이 SLLS로 주어진다면 컵홀더의 위치는 *S*LL*S* 이다. 조금 더 문제를 단순화해보자. 좌석이 SSS이면 컵홀더의 위치는 *S*S*S*이다. 좌석과 좌석 사이에 컵홀더가 놓이는 것보다 좌석의 우측에 컵홀더가 놓인다고 생각하자. 그렇게 하면 SSS에 놓이는 컵홀더의 위치를 S*S*S*로 볼 수 있고 컵홀더의 수는 좌석의 수와 같다. 그리고 좌석의 끝에 컵홀더 하나를 더 놓으면 되니 좌석의 수를 세고 1을 더해주면 된다. 커플석 LL은 2개가 연속으로 주..
5612)터널의 입구와 출구 https://www.acmicpc.net/problem/5612 문제를 잘 읽어야 쉽다. 데이터가 입력 되는 모양새를 추상화해보면 아래 그림과 같다.t = 0인 시점에 터널에 차 2대가 있었고 1분 간 차가 2대 들어오고 3대가 나갔다. 차가 정확이 언제 들어가고 언제 나갔는지 알 수 없어서 t = 1/2일 때 터널에 몇 대의 차가 있는지 알 수 없다. 1분 후인 t = 1일 때 몇 대의 차가 있는 지 정확히 알 수 있다. 문제는 친절하게 t = 0,1,2,...,n인 시점에 터널에 차가 몇 대 있는가를 묻고 있다. 그 중에서 차의 수가 최대가 되는 때를 찾아서 출력하면 된다. 123456789101112131415161718192021222324252627#include#define TRUE 1#de..
3054)피터팬 프레임 https://www.acmicpc.net/problem/3054 피터팬 프레임을 만들기 위해 i와 j값에 따라 '.'이나 '#'을 찍는 것은 어렵다. 그래서 미리 피터팬 프레임과 웬디 프레임을 만들어 두고 스탬프처럼 찍는 것을 생각했다. 이 때 두 가지 정도 생각해봐야 할 것이 있다. 첫째로 프레임을 담아낼 배열의 크기는 프레임이 겹친다는 것을 고려해야 한다. 프레임 배열의 열 길이 = (웬디 or 피터팬 프레임)열 길이 + (열 길이-1) * 단어의 길이 +1(NULL) 프레임 배열의 행 길이 = (웬디 or 피터팬 프레임)행 길이 둘째로 피터팬 프레임과 웬디 프레임이 겹칠 때 웬디 프레임을 위로 드러내야 한다는 것이다. 위 방식은 프레임을 스탬프를 찍을 때 이전 프레임이 덧씌우진다는 문제가 있다. ..
11047)동전 0 https://www.acmicpc.net/problem/11047 문제를 풀어도 개운치가 않아서 다른 풀이를 찾아봤다. 어떻게 하면 이런 생각을 할 수 있을지 의문이 들면서 내가 솔루션을 찾는 방식을 되돌아 볼 필요성을 느꼈다. 4790원이 주어진다. 10종류의 동전을 최소한으로 사용해 4790원을 만들 때 사용된 동전 갯수를 찾아야 한다. 1.동전 배열에서 K = 4200원을 만들기 위한 가장 큰 동전을 찾는다.(1000원) 2.그 동전으로 K = 420790을 나눈 몫을 합산한다.(동전의 갯수 저장) 3.그 동전으로 나눈 나머지로 K를 갱신한다. (K = 200) 4.1000원보다 작은 동전이 되게끔 인덱스를 하나 감소시킨다. K를 나타낼 수 있는 최대 크기의 동전을 찾으면 나머지 돈들은 그 이하의..

티스토리툴바