This problem asks us to change a list of 1's and 2's to a list of 0 or more 1's followed by 0 or more 2's. The trick is to change as few of the digits as possible.
A quick exercise with pencil and paper coupled with a tiny bit of insight yields the idea that one can change 1's to 2's start on the right side of the string and 2's to 1's on the left side of the string. Some combination will have the smallest number of changes.
My program below calculates the counts of changing digits both from left to right and also right to left. It then examines those results to find the location at which the sum of the changes (the point at which we quit changing 2's to 1's and start changing 1's to 2's) is minimized. This is an 'ad hoc' algorithm: Just requires insight, no special theory or background.
#include <stdio.h>
#include <stdlib.h>
main () {
FILE *fin = fopen ("diningb.in", "r");
FILE *fout = fopen ("diningb.out", "w");
int i, n;
int cards[30000+1], ones[30000+1], twos[30000+1], min;
fscanf (fin, "%d", &n);
for (i = 0; i < n; i++)
fscanf (fin, "%d", &cards[i]);
if (cards[0] == 2) ones[0] = 1;
else ones[0] = 0;
for (i = 1; i < n; i++)
if (cards[i] == 2) ones[i] = ones[i-1]+1;
else ones[i] = ones[i-1];
ones[n] = ones[n-1];
if (cards[n-1] == 1) twos[n-1] = 1;
else twos[n-1] = 0;
for (i = n-2; i >= 0; i--)
if (cards[i] == 1) twos[i] = twos[i+1]+1;
else twos[i] = twos[i+1];
twos[n] = 0;
min = twos[0];
for (i = 0; i < n; i++)
if (ones[i] + twos[i+1] < min)
min = ones[i] + twos[i+1];
fprintf (fout, "%d\n", min);
exit (0);
}