11048번: 이동하기
준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는
www.acmicpc.net
<풀이>
코테 대비용으로 백준을 풀면서 골드 3-5사이를 푸는걸 목표로 했는데... 어쩌다보니 오늘은 실1 문제도..하하..
사실 dp + dfs 조합의 문제에 너무 익숙하지 않아서 도전했는데 그냥 dp문제였다.
준규가 3방향으로만 이동가능하기 때문에 현 위치의 사탕개수 + 3방향 중 이동했을 때의 값이 젤 큰 곳 으로 선정하면서
최댓값을 갱신해주면 된다. dp는 식만 잘 세우면 무리가 없지만 그게 젤 어려움 .... 잘하는 방법 뭔데....
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int n,m;
int map[1001][1001];
int dp[1001][1001];
int main(void){
cin>>n>>m;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cin>>map[i][j];
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
dp[i][j] = max(max(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+map[i][j];
}
}
cout<<dp[n][m];
}14430번: 자원 캐기
인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다.
www.acmicpc.net
<풀이>
위의 문제와 아주 유사하다. 얘는 오른쪽이랑 아래로 한 칸만 이동가능하기 때문에 현 위치에서 아래로 이동했을 때 / 오른쪽으로 이동했을 때 둘 중 큰 쪽으로 가면 된다.
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int map[301][301], dp[301][301];
int n,m;
int main(void){
cin>>n>>m;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cin>>map[i][j];
}
}
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
dp[i][j] = max(dp[i-1][j], dp[i][j-1])+map[i][j];
}
}
cout<<dp[n][m];
}
<완탐 >
11170번: 0의 개수
N부터 M까지의 수들을 종이에 적었을 때 종이에 적힌 0들을 세는 프로그램을 작성하라. 예를 들어, N, M이 각각 0, 10일 때 0을 세면 0에 하나, 10에 하나가 있으므로 답은 2이다.
www.acmicpc.net
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
int t;
int main(void){
cin>>t;
while(t--){
int a,b;
cin>>a>>b;
int cnt =0;
for(int i=a; i<=b; i++){
string st = to_string(i);
if(st.size()>1){
for(int j=0; j<st.size(); j++){
if(st[j]=='0') cnt++;
}
}
if(st =="0") cnt++;
}
cout<<cnt<<"\n";
}
}11502번: 세 개의 소수 문제
정수론(수학)에서, 세 개의 소수 문제(3-primes problem) 는 다음과 같은 추측을 말한다. '5보다 큰 임의의 홀수는 정확히 세 개의 소수들의 합으로 나타낼 수 있다. 물론 하나의 소수를 여러 번 더할
www.acmicpc.net
<풀이>
소수 판별은 에라토스테네스의 체 방법 사용
해당 값이 소수 3개의 합으로 가능한지에 판별하며 불가능 할 때의 예외처리를 위해 goto문을 사용했답
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int d[1001];
int t;
int main(void){
cin>>t;
for(int i=2; i<1001; i++){
d[i] = 1;
}
for(int i=2; i*i<1001; i++){
for(int j=i*i; j<1001; j+=i){
if(d[j] == 0) continue;
else d[j] =0;
}
}
while(t--){
int num;
cin>>num;
vector<int> vec;
bool flag = false;
for(int i=2; i<1001; i++){
for(int j=2; j<1001; j++){
for(int k=2; k<1001; k++){
if(d[i] && d[j] && d[k]){
if(i+j+k == num){
cout<<i<<" "<<j<<" "<<k<<"\n";
flag = true;
goto check;
}
}
}
}
}
check:
if(flag == false) cout<<"0";
}
}
'Algorithm > BOJ' 카테고리의 다른 글
| [ 백준 ] 37일차 - 17265번/19699번/1620번 (0) | 2021.09.29 |
|---|---|
| [ 백준 ] 36일차 - 1915번/14925번/15711번/2174번 (0) | 2021.09.28 |
| [ 백준 ] 34일차 (0) | 2021.09.26 |
| [ 백준 ] 33일차 (0) | 2021.09.25 |
| [ 백준 ] 32일차 (0) | 2021.09.24 |