No UserLicense found error when deploying Full Profiles.

When deploying profiles using the step "Full Profiles" your deployment might fail with the following error message:

No UserLicense found

When a profile is created in Salesforce, it has to be linked to a license. This license must exist in the target organization where the profile is being deployed, otherwise it won't be possible to create the profile.

Possible solutions for this error are:

a) Re-create the profile in the source org using a license that exist in the target org.
b) Enable/Purchase/Activate the license on the target organization and deploy the same profile again.

How did we do?