First off, this is amazing directing, I found myself thinking "wow" multiple times. The film won Park Best Director at Cannes last year.

In terms of story this is a hard-to-categorize romance-noir-detective-film. It's a lot less violent/erotic/in-your-face than other work by Park (the vengeance trilogy including Oldboy, or the more recent The Handmaiden) but makes up for it in subtlety and symbolism. Park did this on purpose: in his mind he's always been making love films, but the violence and sex distracted the audience away from the romance, so this time he wanted to focus on it. The result is a romance with a subtle, subdued noir atmosphere and a unique plot that only someone like Park could dream up, over a police procedural backdrop.

Also the poster art is great:

Poster for Decision to Leave, hand-drawn art of the film's two main characters, with mountains and the sea, in a circle on a white background.