To fully understand how problem-solving ability provides adaptive advantages for animals, we should understand the mechanisms that support this ability. Recent studies have highlighted several behavioural traits including persistence, behavioural variety and behavioural/cognitive flexibility that contribute to problem-solving success. However, any increment in these traits will increase time and energy costs in natural conditions, so they are not necessarily advantageous. To examine how behavioural traits vary during learning to solve a problem efficiently, we gave grey squirrels, Sciurus carolinensis, a problem-solving task that required them to obtain out-of-reach but visible hazelnuts by making a lever drop in the laboratory. We recorded persistence, measured as attempt rate, flexibility, measured as the rate of switching between tactics, and behavioural selectivity, measured as the proportion of effective behaviours, in relation to problem-solving efficiency on a trial-by-trial basis. Persistence and behavioural selectivity were found to be directly associated with problem-solving efficiency. These two factors also mediated the effects of flexibility and increased experience. We also found two routes that led to more efficient problem solving across learning trials: increasing persistence or increasing behavioural selectivity. Flexibility was independent from learning. Flexibility could increase problem-solving efficiency, but it also has a time cost; furthermore, it seemed to involve a trade-off with behavioural selectivity, with high flexibility being associated with a higher frequency of some disadvantageous ineffective behaviours. These results suggest that flexibility is an independent cognitive process or behavioural trait that may not always bring advantages to animals.