시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 39 | 22 | 14 | 45.161% |
A,T,G,C からなる DNA 鎖が 2 本あるとき, 一方の先頭と, 他方の末尾の部分に 1 文字以上の連続する共通 部分を持つものをつなげて新しい DNA 鎖を合成する方法が開発された. このとき共通部分は一つにまとめ られる. たとえば,TTTATGC と ATGCAAA は,前者の末尾と後者の先頭に共通部分 ATGC を持つので,つ なげて TTTATGCAAA を合成できる. また,AAA を 2 つ用いて,AAAA と AAAAA のどちらも合成するこ とができる.今,新薬開発のために,研究室にあるいくつかの素 DNA 鎖から,ある DNA 鎖を合成したい.
研究室には N 種類の素 DNA 鎖がある.上記の方法で素 DNA 鎖をつなぎあわせて目的の DNA 鎖を合成 するとき, 最小で何本の素 DNA 鎖が必要となるかを求めるプログラムを作成せよ. ただし,素 DNA 鎖の備 蓄には余裕があるので,同じ種類の素 DNA 鎖を何度でも使うことができる.また,全ての採点データにお いて,目的の DNA 鎖を得る素 DNA 鎖の組み合わせが存在する.
標準入力から以下の入力を読み込め.
標準出力に必要となる素 DNA の本数の最小値を表す 1 つの整数を出力せよ.
5 ATATATGCCCAT ATAT ATG GCCC GCCCAT CAT
4
同じ素 DNA 鎖を何度も使って良いことに注意せよ.
1 AAAAAAAAAA AAA
5
AAA を 2 つ用いて,AAAA と AAAAA のどちらも合成することができる.
2 ATATATATAT ATA TAT
5