BOJ 11583 - 인경호의 징검다리
https://www.acmicpc.net/problem/11583
trailling zero를 최소화 한다는 것은 그 수를 소인수분해 했을때 2와 5의 지수 중 작은 것을 최소화 하는 것과 같다. 2의 지수만을 보고 구한 것과 5의 지수만을 보고 구한 것 중 작은 값이 답이 된다. 이것은 다이나믹 프로그래밍으로 쉽게 구할 수 있다.
BOJ 1034 - 램프
문제 : https://www.acmicpc.net/problem/1034 램프에 $K$번의 조작을 다 하고 나서 최종적으로 몇 개의 행의 불이 완전히 켜져있다고 생각해보자. 불이 완전히 켜져있는 행들은 초기에 서로 켜져있는 불의 상태가 완전히 같았어야한다. 왜냐하면 램프에 가해지는 조작은 열 단위로 가해지기 때문이다. 위 사실을 알고나면, 문제를 이렇게 생각할 수 있다. $K$번의 조작을 해서 어떤 행의 불을 완전히 켤 수 있는가? 만약에 켤 수 있다면 그 행과 똑같이 생긴 행의 수를 답으로 고려해 볼 수 있고, 최종 답은 그러한 행의 수 중 최대가 된다. 이제 $K$번의 조작을 해서 어떤 행의 불을 완전히 켤 수 있는지를 알 수 있으면 되는데, 이는 처음에 꺼져있는 열의 수보다 $K$가 크거나 같을 때 홀짝만 잘 따지면 알 수 있다. 코드 : http://ideone.com/tcrFIU
댓글
댓글 쓰기