본문 바로가기

전체 글

 (84)
백준 9657 돌 게임 3 https://www.acmicpc.net/problem/9657 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 처음 봤을 때도 어려웠는데, 다시봐도 쉽지 않다... 이 문제도 결국에는 처음 몇가지를 하나씩 써내려나가는게 도움이 된다. 그로 인해 어떠한 규칙성을 파악할 가능성이 있기 때문이다. 돌을 1, 3, 4개씩 가져갈 수 있으므로, 돌이 1, 3, 4개씩 처음에 주어진 경우는 당연히 상근이가 무조건 이긴다. (다 가져가면 되니깐) 돌이 5개 주어진 경우를 생각해보자. 돌을 상근이가 4개 갖고 가면 그 다음 창영이가 1개를 들고가서 지게된다! 상근이가 1개 들고 갔어도 창영이가 4개 들고 가버리면 패배하고만다. 하지만 3..
백준 11727 2xn 타일링 2 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 이 문제는 꼭 이전 포스팅 백준 11726: 2xn 타일링을 참조 부탁드린다. 그림 설명이 있으니. 11726과 똑같은 방식으로 푸는데 n-2의 케이스를 2배해주면 된다. 왜냐면 붙여주는 블록의 모양이 2가지이기 때문이다. 11726문제를 완전히 이해한다면 어렵지 않게 풀 수 있는 문제이다. 다이나믹 프로그래밍 Python import sys si = sys.stdin.readline sz, mod = int(1e3)+1, i..
백준 11726 2xn 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 이 문제를 아주 처음 본다면 약간 어려울 수도 있다. 하지만 마음을 가다듬고(?) 하나씩 케이스별로 그림을 몇 개 그려보면 패턴을 이해할 수 있게 된다. 아래의 그림을 보자. 위 그림은 n이 1~4일 때의 상황을 보여준다. n=3일 때는, n=2일 때의 모양에 긴 막대(보라색)를 붙인 2가지의 경우와 n=1일 때의 모양에 누워있는 막대 2개(파랑색)를 붙인 1가지의 경우의 합으로 구할 수 있다. n=4일 때도 마찬가지..
백준 11561 징검다리 https://www.acmicpc.net/problem/11561 11561번: 징검다리 각 테스트 케이스마다 한 줄에 승택이가 밟을 수 있는 최대 징검다리 수를 출력한다. www.acmicpc.net brute force/완전 탐색은 모든 경우의 수를 전부 따져보는 것을 말한다. 여러 알고리즘은 이러한 모든 경우의 수 중에서 확정적으로 들어낼 수 있는 부분을 걸러준다. 이분탐색은 답이 아니라고 확신하는 부분을 절반씩 들어내기에 빠르게 완탐(?!)이 가능해진다. 혹시나 이분탐색이 생소하다면 이 포스팅을 참조 부탁드린다. 이 문제는 왜 이분탐색으로 풀 수 있을까? 주어진 징검다리의 상한값이 1e16으로 너무너무 커서? 그것도 한가지 힌트가 되겠지만, 문제를 잘 생각해보면, 가장 많은 징검다리를 밟는 방법..
백준 1507 궁금한 민호 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 이 문제는 플로이드 와샬을 역으로 활용하면 된다. 조금 생각해보면 직관적으로 그 아이디어가 떠오를 것이다. 그리고 그게 맞다! 플로이드 와샬 알고리즘을 이용해 최단경로를 구할 때, 최소값으로 계속 갱신해준다. 이번에는 그러한 경우가 발생할 때마다 해당 경로를 지워주면 된다. 각 정점들을 연결하는 도로정보가 주어지는데, 이들을 모두 더할 경우, 모든 도로의 가중치 합의 2배가 된다. 그러므로 중..

티스토리툴바