본문 바로가기

정보올림피아드수학

바둑알 이동의 경우의 수 정답) 320 다음과 같이 올수 있는 경우의 수를 더해 보면 320 가지 이다. 이렇게 경우의 수를 모두 세어 주어도 되지만 검은색이 위쪽 흰색 돌에 4번 만나기 위해서는 북동,북,북서 세방향이다. 오른쪽 흰색 돌에 4번만에 만나기 위해서는 북동,동,남동 세방향으로 이동한다. 아래와 왼쪽 역시 동일하다. 결국에는 한방향에 대해서 한번에 3가지씩을 선택할 수 있다. 따라서 한방향으로 이동하는 경우의 수는 3 * 3 * 3 * 3 이다. 이게 4방향이므로 4 * 3 * 3 * 3 * 3 이 된다. 하지만 여기서 각 모서리로 도착하는 4가지 경우가 중복이 발생한다. 왼쪽 상단 모서리로 올라가는 경우 위쪽으로 올라가는 경우와 왼쪽으로 가는 경우의 두가지가 겹친다. 따라서 4귀퉁이값을 빼주면 된다. 더보기
직사각형을 채우는 방법의 개수 구하기 다음 그림과 같은 타일을 이용하여 2 * 5 인 직사각형을 채우는 방법의 수를 구하여라 정답) 1944 문제풀이) 2 * 1 의 크기의 직사각형을 채우는 경우의 수를 확인해 보면 다음과 같이 3가지 이다. 삼각형 2개를 이용하는 경우 2가지 직사각형을 이용하는 경우 1가지 2 * 2 크기의 직사각형을 채우는 경우의 수를 확인 해 보면 2 * 1 을 f(1) 이라고 생각하고 2*0을 f(0) 이라고 생각하면 f(0) 은 공간이 없는 곳에 채우는 개수이므로 안채우는 경우 1가지 이므로 2 * 2 를 f(2) 라고 하면 f(2) 는 f(1) 에 2 * 1 짜리 직사각형 한가지를 붙이는 경우 f(1) * 3 이 된다. 또한 f(0) 에 붙이는 경우는 1*2 짜리 2개를 붙이는 경우를 생각해 보면 3 * 3 = .. 더보기
도형의 넓이 구하기 다음 다각형의 넓이는 얼마입니까? 단 점선의 간격은 1입니다. 정답 : 12 여기서 삼각형의 넓이를 구하는 공식으로 구하기에는 밑변과 높이를 구하기 어렵기 때문에 다음과 같이 사각형을 면적을 먼저 구한 후에 흰색 부분의 넓이를 빼주는 것이 유리합니다. 사각형의 넓이는 6 * 5 = 30 흰색 부분의 삼각형의 넓이는 각각 3 * 6 / 2 = 9 2 * 4 / 2 = 4 2 * 5 / 2 = 5 이므로 18 따라서 30 - 18 = 12 가 됩니다. 더보기
도형 나누기 다음 그림에서 정사각형을 두개로 나누어서 모양과 크기가 서로 같게 하고 A,B,C,D,E 가 각각 하나씩 포함되게 도형을 만들 수 있습니까? 만들 수 있다면 어떤 모양입니까? 정답) 가능 똑같은 모양으로 각각 하나씩 포함을 해야 되므로 AA,BB,CC 를 분리 한 후에 각각을 포함할 수 있는 경로를 찾아 보면 다음과 같은 모양을 만들수 있다. 1단계로 이런 모양으로 분리를 하면 E는 노랑색이 되는 것을 확인 할 수 있다. 여기서 E는 노란색이므로 이렇게 같은 쌍으로 나누면 B는 노랑색이어야 하므로 위와 같은 형식으로 분리를 할 수 있다. 이러한 방법 말고도 여러가지가 있으므로 직접 분해 해 보면 더 좋을것 같네요. 더보기
사탕 먹기 게임 A와 B 2개의 그릇에 사탕이 10개 11개가 들어 있습니다. 갑과 을은 다음과 같은 규칙으로 접시에 있는 사탕을 먹거나 이동시킵니다. 규칙1) 한번에 A 또는 B 그릇에 있는 사탕 2개를 먹을 수 있습니다. 규칙2) A그릇에 있는 사탕 1개를 B그릇에 옮길 수 있습니다. 규칙3) 자신의 차례에 규칙1 또는 규칙2를 수행할 수 없다면 게임이 끝나며 해당 차례의 자신은 지는 것입니다. 갑이 먼저 수행 하고 이 규칙대로 최선을 다한다면 이 게임에서 지는 사람은 누구 입니까? 정답) 을 다음과 같이 표를 만들어 봅니다. 이기는 사람은 자신보다 왼쪽으로 두칸(B를 2개 먹은 경우),위쪽으로 두칸(A를 2개 먹은 경우) 혹은 오른쪽 대각선으로 한칸(A에서 B로 이동 시키는 경우)을 밀어 줄 수 있습니다. 이렇게 .. 더보기
개미의 이동 가로 길이가 6이고 세로 길이가 4인 2차원 격자 공간에서 개미는 다음과 같이 오른쪽 위 45도 방향으로 일정한 속력으로 이동한다. 처음에 (4,1)에서 출발한 개미는 1시간 후에(4+1,1+1) 로 옮겨진다. 단, 이 속력으로 움직이다가 경계면에 부딪치면 같은 속력으로 반사되어 움직인다.아래 그림은 이동하는 경로를 보여 주며 8시간 후에는 (0,1) 위치로 이동하는 것을 보여 준다. 이렇게 이동할때 240 시간 후에 개미의 위치는 어디인지 (x,y) 형식으로 답변하시오(답변 예:(0,1) ) 문제풀이) 개미의 이동경로를 다음과 같이 오른쪽으로 계속 직진한다고 가정을 해 봅니다. 공간을 확장했을때 위와 같이 이동을 하게 되는데 이때 6*4 의 크기에서 6에서 꺽이면서 다음과 같이 경로가 변경 되는 것을 .. 더보기
제일 짧은 노선의 경로 갯수 구하기 다음의 그림에서 A에서 B까지 가는 최단 경로의 갯수는 몇개입니까?(숫자만 적어 주세요.) 문제 풀이) 이 문제에서 최단거리를 가기 위새서는 다음의 두군데 경로를 지나는 경로 입니다. 따라서 A부터 B까지 가는 경로의 개수를 확인하면 다음과 같습니다. 따라서 모든 경로의 갯수는 4 * 3 * 10 = 120 이 됩니다. 더보기
이진수를 십진수로 변경하는 방법 이진수를 십진수로 변경 하는 방법은 다음과 같다. 1111...1 처럼 1 이 n 개가 있는 경우 앞에서 부터 1 * 2 ( n -1 승) + 1 * 2 ( n - 2 승) .... + 1 * 2 ( 0 승) 으로 구한다. 1111 의 십진수는 1 * 2(3승) + 1 * 2(2승) + 1 * 2(1승) + 1 * 2(0승) = 8 + 4 + 2 + 1 = 15 와 같이 구해진다. 프로그램으로 구현 시 n 개 만큼 루프를 돌면서 바로 앞의 데이터에 2를 곱한 후 현재의 데이터를 합하면 된다. 예를 들면 1011 의 데이터 값을 구할때 다음과 같다. 0 * 2 + 1 = 1 1 * 2 + 0 = 2 2 * 2 + 1 = 5 5 * 2 + 1 = 11 더보기

티스토리툴바