网络喷子键盘侠的输入框上已经键入了一句喷人的话,现在他的键盘上只有两个键可用
C:拷贝,可以把输入框的所有内容拷贝下来
P:粘贴,可以在输入框结尾处添加刚刚拷贝的所有内容
请问他至少需要按多少次,可以把输入框里的话复制N次发送出去呢?

样例

如果不可能,则返回{-1, “”}。
我们保证 N >= 0

1
2
3
4
5
6
7
8
9
10
11
N = 0
做不到,返回 -1, ""
N = 1
0次:
N = 2
2次:CP
N = 12
7次:CPCPCPP

分析

有的同学可能会误以为这是一个动态规划的题目,
可能是因为有一道题叫做“矩阵乘法”,这个题目相比来说很类似。

实际上因为它可以完全用贪心法,所以没有必要动态规划。

直接采用因式分解,然后把因子加起来就可以了。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// KeyPress accepts target number of repeat times on the screen,
// returns times of key pressing & key pressing sequence
func KeyPress(N int) (int, string) {
var seq string
if N <= 0 {
return -1, seq
}
var result = 0
for i := 2; i <= N; {
if N%i == 0 {
N = N / i
result += i
seq = seq + "C"
for j := 1; j < i; j++ {
seq = seq + "P"
}
} else {
i++
}
}
return result, seq
}