Solution:

In an $n$-step staircase the vertical toothpicks number $(1 + 2 + \cdots + n) + n = \tfrac{n(n+1)}{2} + n,$ and there are just as many horizontal ones. That's a total of $n(n+1) + 2n = n(n+3).$ Check: $n = 3$ gives $18,$ as it should. Now solve $n(n+3) = 180.$ This factors as $(n-12)(n+15) = 0,$ so $n = 12.$ Therefore, the answer is C.