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 destination 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 destination org.
b) Enable/Purchase/Activate the license on the destination organization and deploy the same profile again.

How did we do?