일시
22.07.20 14:00 ~ 17:00
목표
알고리즘 실력 향상을 위해 백준에서 출제하는 문제들을 풀어본다.
사용 언어
C++
1번 문제
https://www.acmicpc.net/problem/1027
결과
빌딩이 보이려면 현재 있는 빌딩에서 해당하는 빌딩의 기울기가 전의 빌딩의 기울기 보다 작아야한다. 즉, 멀리 있는 빌딩일수록 기울기가 커야한다.
현재 인덱스의 빌딩으로부터 왼쪽의 빌딩 오른쪽의 빌딩 모두다 구해주고 기울기가 커지는 빌딩의 수를 구한다.
0번째 인덱스 빌딩과 N-1번째 빌딩은 각각 왼쪽과 오른쪽에 건물이 없기때문에 한쪽만 구해준다.
2번 문제
https://www.acmicpc.net/problem/1062
결과
readCnt함수는 배운 알파벳들을 가지고 이 단어를 읽을 수 있는지 판별하는 함수이다.
하나씩 알파벳이 읽을 수 있는 true이면 끝까지 검사하고 하나라도 false이면 못 읽는다고 판별하고 넘어간다.
배울 수 있는 알파벳의 모든 경우의 수를 dfs로 구한다.
최대치로 알파벳을 배웠다면 읽을 수 있는지 확인하는 readCnt함수를 부른다.
모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 때문에 a, n, t, i, c는 반드시 알아야한다. 즉, 배울 수 있는 알파벳의 개수가 5개보다 작으면 아무것도 읽을 수 없다. 5개 이상 배울 수 있드면 a, n, t, i, c를 반드시 배우고 다른 알파벳들도 dfs로 배운다.
3번 문제
https://www.acmicpc.net/problem/1520
결과
왼쪽 위에서 오른쪽 아래로 가는 길을 찾는 문제인데 단순 dfs로 풀면 지도의 크기가 500 X 500도 있으므로 굉장히 많은 경우의 수가 있어 시간을 충족시키지 못한다.
그러므로 dp랑 섞어서 최소 길의 수를 dp에 저장한다.
지도를 입력 받을 때 dp에는 -1을 저장한다. 0으로 초기화 하면 갈수 없는 길이 생길때 구분할 수 없기 때문에 -1로 초기화 해준다.
