본문 바로가기

분류 전체보기

 (81)
2965)캥거루 세 마리 https://www.acmicpc.net/problem/2965 수직선 위에 서로 다른 정수점 세 개가 주어진다. 가장 바깥쪽에 있는 정수점 하나는 다른 두 정수점 사이로 뛰어들 수 있지만 다른 정수점과 겹칠 수는 없다. 이 규칙으로 정수점 사이를 뛰어들 때 최대한 많이 뛰는 횟수를 찾는 문제다. 예를들어 정수점이 1,4,9라고 하자.정수점은 위 그림과 같다. 여기서 1이 4~9 사이로 뛰어들든가 9가 1~4 사이로 뛰어드는 방법이 있다. 딱보기에도 1이 4~9사이로 뛰어드는 방법이 4~9의 간격이 크기 때문에 많이 뛸 수 있어 보인다. 여기서 가능하면 정수점 사이의 간격을 크게만들어주는 방향으로 뛰어드는 것이 좋다는 것을 알 수 있다. 정수점 1이 4옆으로 뛰어들었다. 애매모호하게 6이나 7로 뛰어든..
10757)큰 수 A+B https://www.acmicpc.net/problem/10757 두 수를 더해 그 결과를 출력하는 쉬운 문제처럼 보이지만 더하는 두 수가 10^10000보다 작다. int나 long long 타입으로 위처럼 큰 수를 다룰 수 없기 때문에 문자열로 처리해야 한다. 두 수의 합을 구현하려면 sum과 carry를 고려해야 한다. 두 수의 길이가 어떻든 맨 마지막 자리수 끼리 맞추고 각 자리수들을 더한다. 예를 들어 1234 + 987을 더할 때 가장 마지막 자리끼리 더하면 sum = 11이다. sum>10이므로 carry가 발생했다. sum에서 10을 빼주고 carry에 1을 대입한다. sum을 result 배열에 넣어준다. 두 번째 자리를 더하면 sum = 3+8+carry 이므로 sum = 12이다. ..
15501)부당한 퍼즐 https://www.acmicpc.net/problem/15501 처음에 1~n에서 한 번씩 숫자가 나오는 수열이 주어진다. 1 2 3 4 5처럼 주어질 수도 있고 3 2 5 1 4처럼 특별한 규칙없이 수열이 주어질 수 있다. 처음 주어진 수열을 A라고 하자. 게임 규칙에 따라 수열 A로 가능한 연산은 뒤집기와 왼쪽, 오른쪽 밀기이다. 수열 A가 1 2 3 4 5일때 이 수열을 뒤집으면 5 4 3 2 1이다. 수열 A를 왼쪽으로 밀어내면 2 3 4 5 1, 오른쪽으로 밀어내면 5 1 2 3 4이다. 이후 수열 B가 주어지는데 수열 A로 위 연산을 통해 수열 B로 만들 수 있는 지 알아내야 한다. 뒤집기, 왼쪽, 오른쪽 밀어내기 연산을 해도 바뀌지 않는 것이 있다. 바로 수열의 순서이다. 예를들어 수열 ..
16396)선 그리기 https://www.acmicpc.net/problem/16396 선분의 시작점과 끝점을 입력으로 받는다. 요것을 그대로 일차원 배열에 넣으면 된다. 예를들어 1 10은 1부터10까지 선분을 말하는데 일차원 1~9까지 각 방을 TRUE로 바꿔주면 된다. 총 길이는 10000을 넘지 않으므로 미리 10000개의 방을 잡아놓고 입력에서 최소 시작점과 최대 끝점을 찾아서 최소 시작점부터 최대 끝점까지 TRUE인 것의 수를 세면 된다. 123456789101112131415161718192021222324252627282930313233#include#define MAX(A,B) (A>B)?A:B#define MIN(A,B) (A
14891)톱니바퀴 https://www.acmicpc.net/problem/14891 똑바로 글을 읽어야 한다는 걸 깨닫게 해준 문제였다. 톱니가 어떻게 회전하는 지를 잘 파악해야 한다. 첫 번째로 문제를 풀 때 톱니가 회전한 후, 양쪽의 톱니가 맞물리는 지 검사했다. 두 번쨰로 문제를 풀 땐 선택한 톱니가 회전하기 전 양쪽의 톱니가 맞물리는 지 검사하고 첫 번째 사용했던 코드를 그대로 가져다 썼다. 세 번째로 문제를 풀었을 때 제대로 비로소 문제를 이해하게 됬는데 =_=... 톱니가 회전하기 전에 톱니들 끼리 맞물렸을 때 극이 같은 지, 다른 지 검사하고 다른 경우 회전방향을 토글시킨다. 회전시키기 전에 각 톱니의 회전 방향을 배열에다가 저장해야 한다. 그리고 저장해둔 회전 방향에 따라 톱니를 회전시켜야 한다. 문제를 ..
2583)영역 구하기 https://www.acmicpc.net/problem/2583 흰 배추벌레 문제랑 비슷하다. 주어진 입력을 처리하는 방법부터 생각해보자. 직사각형의 영역을 입력할 때 왼쪽 아래가 시작점이고 오른쪽 위가 끝나는 점이다. 이 점들은 아래 그림처럼 x,y 좌표계의 좌표다. 전체 영역에서 어떤 영역의 면적을 표현하기 위해 2차원 배열을 사용할텐데 2차원 배열은 아래 그림처럼 i,j의 증가 방향이 x,y 좌표계와 일치하지 않는다는 점을 유의해야 한다.이 문제는 연속하는 흰색 영역의 갯수와 그 크기를 출력하는 문제다. 위 그림에서 흰색 영역의 갯수는 3개이고 각각의 크기는 1, 7, 13이다. 연속하는 영역의 크기를 구하기 위해 재귀적으로 4방향 탐색 방법을 사용할 것이다. 특정 영역의 면적은 TRUE로 표현했..
10158)개미 https://www.acmicpc.net/problem/10158 가로 길이가 w, 세로 길이가 h인 격자 공간에 (p,q)에 개미를 두면 1시간 후에 개미는 (p+1,q+1)으로 이동한다. 개미가 격자 공간의 경계에 부딪히면 운동방향이 바뀐다. 이것을 쉽게 표현하기 위해 개미는 한 시간 뒤에 (p+dx, q+dy)로 이동한다고 하자. (초기 dx = 1, dy = 1) 개미가 x = 0, x = w에 부딪힐 때 x축 이동 방향이 반대로 바뀐다. 예를들어 개미의 이동 방향이 dx = 1, dy = -1일 때 x = w에 부딪히면 dx = -1, dy = -1로 바뀐다. 개미가 y = 0, y = h에 부딪힐 때 y축 이동 방향이 반대로 바뀐다. 12345678910111213141516171819202..
10159)저울 https://www.acmicpc.net/problem/10159 물체의 무게는 구체적으로 알 수 없지만 물체 끼리 비교해서 얻은 대소 관계는 알 수 있다. 주어진 예제에서 각 물체의 대소 관계는 아래와 같다. 1>2, 2>3, 3>4, 5>4, 6>5 각각의 물체를 비교한 결과를 이어 붙이면 아래처럼 정리할 수 있다. 1>2>3>4 6>5>4 1번 물체는 1,2,3,4와 대소 관계를 확인할 수 있지만 5,6과 대소 관계는 확인할 수 없다. 이 관계를 조금 더 쉽게 표현할 수 없을까 고민하다가 방향성 그래프와 유사한 면이 있음을 알게됬다. 4번 물체는 1,2,3번 물체와 5,6번 물체와 대소 관계를 알 수 있는데, 1,2,3번 물체는 5,6번 물체와 대소 관계를 알 수 없다. 여기서 1,2,3번은 4번..

티스토리툴바