Can this problem be solved using deep learning?
The problem is a case for "deep learning", I think, and I would start with boosting. I have good experiance with catboost (in Python). It can handle factors very well ("catfeatures", encoded as dummies) and it is relatively fast. Also lightgbm might be a good option. Also xgboost is an option.

I think data-wise one hot encoding and scaling is the first thing to do. Things beyond that is a bit try and error. The most important part might be that you tune your hyperparameter well (during boosting). 

Catboost (Python): https://catboost.ai/docs/concepts/python-usages-examples.html
LightGBM (Python): https://lightgbm.readthedocs.io/en/latest/Python-Intro.html

Happy coding!