Putting data in program memory on Arduboy

I guess that means it has to go into RAM.

That doesn't mean that the array needs to use 8 times as much memory as needed. You are storing one bit in each byte. Store 8 bits in each byte and use 1/8th the memory.