This game was listed by "30years old Korean" (30yk) in the comments section of Haze's WIP blog. He found them listed on the Korea Media Rating Board website. Sadly, the links he posted aren't working anymore.
Should be a Tetris Attack type puzzle.
It was released in December 1995, even though the title screen says 1996.