2020. 3. 21. 14:17, 알고리즘/ETC
2020 상반기 코딩테스트 모의고사 풀이.pdf0.89MB
문제 링크 : https://www.acmicpc.net/contest/view/505
--------------- 스포방지 ---------------
I. 스티커 붙이기
C++
#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int note[42][42];
int r, c;
int paper[12][12];
// paper를 90도 회전하는 함수
void rotate(){
int tmp[12][12];
for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
tmp[i][j] = paper[i][j];
for(int i = 0; i < c; i++)
for(int j = 0; j < r; j++)
paper[i][j] = tmp[r-1-j][i];
swap(r, c);
}
// note의 (x,y)에 모눈종이의 (0,0)이 올라가게 스티커를 붙일 수 있는지 판단하는 함수. 가능할 경우 note를 갱신한 후 true를 반환.
bool pastable(int x, int y){
for(int i = 0; i < r; i++){
for(int j = 0; j < c; j++){
if(note[x+i][y+j] == 1 && paper[i][j] == 1)
return false;
}
}
for(int i = 0; i < r; i++){
for(int j = 0; j < c; j++){
if(paper[i][j] == 1)
note[x+i][y+j] = 1;
}
}
return true;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> k;
while(k--){
cin >> r >> c;
for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
cin >> paper[i][j];
for(int rot = 0; rot < 4; rot++){
bool is_paste = false; // 해당 스티커를 붙였는가?
for(int x = 0; x <= n-r; x++){
if(is_paste) break;
for(int y = 0; y <= m-c; y++){
if(pastable(x, y)){
is_paste = true;
break;
}
}
}
if(is_paste) break;
rotate();
}
}
int cnt = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cnt += note[i][j];
cout << cnt << '\n';
}
JAVA
import java.util.*;
import java.io.*;
import java.lang.*;
public class Main{
static int n, m, k;
static int[][] note;
static int r, c;
static int[][] paper;
static void rotate(){
int[][] tmp = new int[r][c];
for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
tmp[i][j] = paper[i][j];
for(int i = 0; i < c; i++)
for(int j = 0; j < r; j++)
paper[i][j] = tmp[r-1-j][i];
int t = r;
r = c;
c = t;
}
static boolean pasteable(int x, int y){
for(int i = 0; i < r; i++){
for(int j = 0; j < c; j++){
if(note[x+i][y+j] == 1 && paper[i][j] == 1)
return false;
}
}
for(int i = 0; i < r; i++){
for(int j = 0; j < c; j++){
if(paper[i][j] == 1)
note[x+i][y+j] = 1;
}
}
return true;
}
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
note = new int[n][m];
for(int zz = 0; zz < k; zz++){ // k번 반복
st = new StringTokenizer(br.readLine(), " ");
r = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
paper = new int[Math.max(r,c)][Math.max(r,c)];
for(int i = 0; i < r; i++){
st = new StringTokenizer(br.readLine(), " ");
for(int j = 0; j < c; j++)
paper[i][j] = Integer.parseInt(st.nextToken());
}
for(int rot = 0; rot < 4; rot++){
boolean is_paste = false;
for(int x = 0; x <= n-r; x++){
if(is_paste) break;
for(int y = 0; y <= m-c; y++){
if(pasteable(x,y)){
is_paste = true;
break;
}
}
}
if(is_paste) break;
if(rot != 3) rotate();
}
}
int cnt = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cnt += note[i][j];
bw.write(Integer.toString(cnt) + "\n");
br.close();
bw.close();
}
}
Python
import sys
input = sys.stdin.readline
n,m,k = map(int, input().split())
note = [[0]*m for i in range(n)]
def rotate(paper):
r, c = len(paper), len(paper[0])
return [[paper[r-1-j][i] for j in range(r)] for i in range(c)]
'''
tmp = [[0]*r for i in range(c)]
for i in range(c):
for j in range(r):
tmp[i][j] = paper[r-1-j][i]
return tmp
'''
def pastable(x, y):
if any(note[x+i][y+j] == 1 and paper[i][j] == 1 for i in range(r) for j in range(c)):
return False
for i in range(r):
for j in range(c):
if paper[i][j] == 1:
note[x+i][y+j] = 1
return True
'''
def pastable(x, y):
for i in range(r):
for j in range(c):
if(note[x+i][y+j] == 1 and paper[i][j] == 1):
return False
for i in range(r):
for j in range(c):
if paper[i][j] == 1:
note[x+i][y+j] = 1
return True
'''
for _ in range(k):
r, c = map(int, input().split())
paper = [list(map(int, input().split())) for _ in range(r)]
for rot in range(4):
is_paste = False
for x in range(n-r+1):
if is_paste: break
for y in range(m-c+1):
if pastable(x,y):
is_paste = True
break
if is_paste: break
if rot != 3:
paper = rotate(paper)
r, c = c, r
sys.stdout.write(str(sum([sum(L) for L in note])))
II. Gaaaaaaaaaarden
C++ (next_permutation)
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n,m,g,r;
int board[52][52];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
vector<pair<int,int> > cand;
int candsz;
const int EMPTY = 0;
const int GREEN = 1;
const int RED = 2;
const int FLOWER = 3;
// next_permutaion을 위한 변수, cand가 7이고 g=1,r=4일 때 {0,0,1,2,2,2,2}
int brute[10];
int solve(){
int cnt = 0;
pair<int,int> state[52][52]; // {arrival time, color}
queue<pair<int,int>> q;
for(int i = 0; i < candsz; i++){
if(brute[i] == GREEN || brute[i] == RED){
state[cand[i].X][cand[i].Y] = {0, brute[i]};
q.push(cand[i]);
}
}
while(!q.empty()){
auto cur = q.front(); q.pop();
int curtime = state[cur.X][cur.Y].X;
int curcolor = state[cur.X][cur.Y].Y;
if(state[cur.X][cur.Y].Y == FLOWER) continue;
for(int dir = 0; dir < 4; dir++){
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(board[nx][ny] == 0) continue;
if(state[nx][ny].Y == EMPTY){
state[nx][ny] = {curtime+1, curcolor};
q.push({nx,ny});
}
else if(state[nx][ny].Y == RED){
if(curcolor == GREEN && state[nx][ny].X == curtime+1){
cnt++;
state[nx][ny].Y = FLOWER;
}
}
else if(state[nx][ny].Y == GREEN){
if(curcolor == RED && state[nx][ny].X == curtime+1){
cnt++;
state[nx][ny].Y = FLOWER;
}
}
}
}
return cnt;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> g >> r;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> board[i][j];
assert(board[i][j] >= 0 && board[i][j] <= 2);
if(board[i][j] == 2)
cand.push_back({i,j});
}
}
candsz = cand.size();
fill(brute+candsz-g-r, brute+candsz-r,GREEN);
fill(brute+candsz-r, brute+candsz,RED);
int mx = 0;
do{
mx = max(mx, solve());
}while(next_permutation(brute, brute+candsz));
cout << mx << '\n';
}
C++ (백트래킹)
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n,m,g,r;
int board[52][52];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
vector<pair<int,int> > cand;
int candsz;
const int EMPTY = 0;
const int GREEN = 1;
const int RED = 2;
const int FLOWER = 3;
// backtracking을 위한 변수
bool isused[10];
// 초록/빨강 배양액으로 선택한 위치의 index
int chosen_g[5], chosen_r[5];
int mx;
int solve(){
int cnt = 0;
pair<int,int> state[52][52]; // {arrival time, color}
queue<pair<int,int>> q;
for(int i = 0; i < g; i++){
state[cand[chosen_g[i]].X][cand[chosen_g[i]].Y] = {0, GREEN};
q.push(cand[chosen_g[i]]);
}
for(int i = 0; i < r; i++){
state[cand[chosen_r[i]].X][cand[chosen_r[i]].Y] = {0, RED};
q.push(cand[chosen_r[i]]);
}
while(!q.empty()){
auto cur = q.front(); q.pop();
int curtime = state[cur.X][cur.Y].X;
int curcolor = state[cur.X][cur.Y].Y;
if(state[cur.X][cur.Y].Y == FLOWER) continue;
for(int dir = 0; dir < 4; dir++){
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(board[nx][ny] == 0) continue;
if(state[nx][ny].Y == EMPTY){
state[nx][ny] = {curtime+1, curcolor};
q.push({nx,ny});
}
else if(state[nx][ny].Y == RED){
if(curcolor == GREEN && state[nx][ny].X == curtime+1){
cnt++;
state[nx][ny].Y = FLOWER;
}
}
else if(state[nx][ny].Y == GREEN){
if(curcolor == RED && state[nx][ny].X == curtime+1){
cnt++;
state[nx][ny].Y = FLOWER;
}
}
}
}
return cnt;
}
void select_r(int idx){
if(idx == r){
mx = max(mx, solve());
return;
}
int cur = 0;
if(idx != 0) cur = chosen_r[idx-1]+1;
while(cur < candsz){
if(isused[cur]){
cur++;
continue;
}
isused[cur] = true;
chosen_r[idx] = cur;
select_r(idx+1);
isused[cur] = false;
cur++;
}
}
void select_g(int idx){
if(idx == g){
select_r(0);
return;
}
int cur = 0;
if(idx != 0) cur = chosen_g[idx-1]+1;
while(cur < candsz){
isused[cur] = true;
chosen_g[idx] = cur;
select_g(idx+1);
isused[cur] = false;
cur++;
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> g >> r;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> board[i][j];
if(board[i][j] == 2)
cand.push_back({i,j});
}
}
candsz = cand.size();
select_g(0);
cout << mx << '\n';
}
JAVA
import java.util.*;
import java.io.*;
public class Main{
static int n, m, g, r;
static int[][] board;
static int dx[] = {1,0,-1,0};
static int dy[] = {0,1,0,-1};
static int mx = 0;
static int[] candx = new int[10];
static int[] candy = new int[10];
static int candsz = 0;
static final int EMPTY = 0;
static final int GREEN = 1;
static final int RED = 2;
static final int FLOWER = 3;
static boolean[] isused = new boolean[10];
static int[] chosen_g = new int[5];
static int[] chosen_r = new int[5];
static int solve(){
int cnt = 0;
Pair[][] state = new Pair[n][m]; // {arival time, color}
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
state[i][j] = new Pair();
Queue<Pair> q = new LinkedList<>();
for(int i = 0; i < g; i++){
state[candx[chosen_g[i]]][candy[chosen_g[i]]] = new Pair(0, GREEN);
q.add(new Pair(candx[chosen_g[i]],candy[chosen_g[i]]));
}
for(int i = 0; i < r; i++){
state[candx[chosen_r[i]]][candy[chosen_r[i]]] = new Pair(0, RED);
q.add(new Pair(candx[chosen_r[i]],candy[chosen_r[i]]));
}
while(!q.isEmpty()){
Pair cur = q.poll();
int curtime = state[cur.x][cur.y].x;
int curcolor = state[cur.x][cur.y].y;
if(state[cur.x][cur.y].y == FLOWER) continue;
for(int dir = 0; dir < 4; dir++){
int nx = cur.x + dx[dir];
int ny = cur.y + dy[dir];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(board[nx][ny] == 0) continue;
if(state[nx][ny].y == EMPTY){
state[nx][ny] = new Pair(curtime+1,curcolor);
q.add(new Pair(nx,ny));
}
else if(state[nx][ny].y == RED){
if(curcolor == GREEN && state[nx][ny].x == curtime+1){
cnt++;
state[nx][ny].y = FLOWER;
}
}
else if(state[nx][ny].y == GREEN){
if(curcolor == RED && state[nx][ny].x == curtime+1){
cnt++;
state[nx][ny].y = FLOWER;
}
}
}
}
return cnt;
}
static void select_r(int idx){
if(idx == r){
mx = Math.max(mx, solve());
return;
}
int cur = 0;
if(idx != 0) cur = chosen_r[idx-1]+1;
while(cur < candsz){
if(isused[cur]){
cur++;
continue;
}
isused[cur] = true;
chosen_r[idx] = cur;
select_r(idx+1);
isused[cur] = false;
cur++;
}
}
static void select_g(int idx){
if(idx == g){
select_r(0);
return;
}
int cur = 0;
if(idx != 0) cur = chosen_g[idx-1]+1;
while(cur < candsz){
isused[cur] = true;
chosen_g[idx] = cur;
select_g(idx+1);
isused[cur] = false;
cur++;
}
}
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
g = Integer.parseInt(st.nextToken());
r = Integer.parseInt(st.nextToken());
board = new int[n][m];
for(int i = 0; i < n; i++){
st = new StringTokenizer(br.readLine(), " ");
for(int j = 0; j < m; j++){
board[i][j] = Integer.parseInt(st.nextToken());;
if(board[i][j] == 2){
candx[candsz] = i;
candy[candsz] = j;
candsz++;
}
}
}
select_g(0);
bw.write(Integer.toString(mx) + "\n");
br.close();
bw.close();
}
static class Pair{
public int x, y;
Pair(int x, int y){
this.x = x;
this.y = y;
}
Pair(){
this.x = 0;
this.y = 0;
}
}
}
Python (백트래킹)
import sys
from collections import deque
input = sys.stdin.readline
EMPTY, GREEN, RED, FLOWER = 0, 1, 2, 3
n,m,g,r = 0, 0, 0, 0
board = []
dx = [1,0,-1,0]
dy = [0,1,0,-1]
cand = [] # 좌표를 담을 에정
candsz = 0
isused = [False]*10
chosen_g = [0]*5
chosen_r = [0]*5
mx = 0
# popleft, append
def solve():
cnt = 0
state = [[[0]*2 for i in range(m)] for j in range(n)]
q = deque()
for i in range(g):
state[cand[chosen_g[i]][0]][cand[chosen_g[i]][1]] = [0, GREEN]
q.append(cand[chosen_g[i]])
for i in range(r):
state[cand[chosen_r[i]][0]][cand[chosen_r[i]][1]] = [0, RED]
q.append(cand[chosen_r[i]])
while q:
cur = q.popleft()
curtime, curcolor = state[cur[0]][cur[1]]
if state[cur[0]][cur[1]][1] == FLOWER: continue
for dir in range(4):
nx = cur[0]+dx[dir]
ny = cur[1]+dy[dir]
if nx < 0 or nx >= n or ny < 0 or ny >= m: continue
if board[nx][ny] == 0: continue
if state[nx][ny][1] == EMPTY:
state[nx][ny] = [curtime+1,curcolor]
q.append([nx,ny])
elif state[nx][ny][1] == RED:
if curcolor == GREEN and state[nx][ny][0] == curtime+1:
cnt += 1
state[nx][ny][1] = FLOWER
elif state[nx][ny][1] == GREEN:
if curcolor == RED and state[nx][ny][0] == curtime+1:
cnt += 1
state[nx][ny][1] = FLOWER
return cnt
def select_r(idx):
global mx
if idx == r:
mx = max(mx, solve())
return None
cur = 0
if idx != 0: cur = chosen_r[idx-1] + 1
while cur < candsz:
if isused[cur]:
cur += 1
continue
isused[cur] = True
chosen_r[idx] = cur
select_r(idx+1)
isused[cur] = False
cur += 1
def select_g(idx):
if idx == g:
select_r(0)
return None
cur = 0
if idx != 0: cur = chosen_g[idx-1] + 1
while cur < candsz:
isused[cur] = True
chosen_g[idx] = cur
select_g(idx+1)
isused[cur] = False
cur += 1
n,m,g,r = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
for j in range(m):
if board[i][j] == 2:
cand.append([i,j])
candsz = len(cand)
select_g(0)
sys.stdout.write(str(mx)+"\n")
Python (itertools.combinations)
import sys
from collections import deque
import itertools
input = sys.stdin.readline
EMPTY, GREEN, RED, FLOWER = 0, 1, 2, 3
n,m,g,r = 0, 0, 0, 0
board = []
dx = [1,0,-1,0]
dy = [0,1,0,-1]
cand = [] # 좌표를 담을 에정
candsz = 0
chosen_g = [0]*5
chosen_r = [0]*5
mx = 0
# popleft, append
def solve():
cnt = 0
state = [[[0]*2 for i in range(m)] for j in range(n)]
q = deque()
for i in range(g):
state[cand[chosen_g[i]][0]][cand[chosen_g[i]][1]] = [0, GREEN]
q.append(cand[chosen_g[i]])
for i in range(r):
state[cand[chosen_r[i]][0]][cand[chosen_r[i]][1]] = [0, RED]
q.append(cand[chosen_r[i]])
while q:
cur = q.popleft()
curtime, curcolor = state[cur[0]][cur[1]]
if state[cur[0]][cur[1]][1] == FLOWER: continue
for dir in range(4):
nx = cur[0]+dx[dir]
ny = cur[1]+dy[dir]
if nx < 0 or nx >= n or ny < 0 or ny >= m: continue
if board[nx][ny] == 0: continue
if state[nx][ny][1] == EMPTY:
state[nx][ny] = [curtime+1,curcolor]
q.append([nx,ny])
elif state[nx][ny][1] == RED:
if curcolor == GREEN and state[nx][ny][0] == curtime+1:
cnt += 1
state[nx][ny][1] = FLOWER
elif state[nx][ny][1] == GREEN:
if curcolor == RED and state[nx][ny][0] == curtime+1:
cnt += 1
state[nx][ny][1] = FLOWER
return cnt
n,m,g,r = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
for j in range(m):
if board[i][j] == 2:
cand.append([i,j])
candsz = len(cand)
for c1 in itertools.combinations(range(candsz), g+r):
for c2 in itertools.combinations(range(g+r), g):
ridx, gidx = 0, 0
for i in range(g+r):
if i in c2:
chosen_g[gidx] = c1[i]
gidx += 1
else:
chosen_r[ridx] = c1[i]
ridx += 1
mx = max(mx, solve())
sys.stdout.write(str(mx)+"\n")
'알고리즘 > ETC' 카테고리의 다른 글
아주 간단한 풀이 스케치 (13) | 2021.09.11 |
---|---|
코딩테스트 언어 선택에 대한 팁(C++ vs Python) (4) | 2021.01.05 |
알고리즘/코딩테스트를 독학하는 방법에 대한 개인적인 생각 (24) | 2020.07.13 |
2020/03/21 코드들 (42) | 2020.03.21 |
3/21에 코딩테스트 대비 모의고사를 진행합니다. (1) | 2020.02.25 |
삼성역량테스트 A형 Cheat Sheet (6) | 2019.09.06 |
온코더를 참가해본 소감과 개인적인 의견 (1) | 2019.02.16 |
Comments
-
https://ideone.com/YVBRUw
-
http://colorscripter.com/s/zzfx0Vf
1번 테케는 다 맞은거 같은데 바로 틀렸습니다 나오네요 ㅠㅠ -
http://colorscripter.com/s/6GOvTdU
리뷰 요청드립니다!!
-
https://ideone.com/ZcjawZ
저도 1번 테케 다 맞고 틀렸습니다 ㅠ -
https://ideone.com/hJ6LXk
1번 81%에서 자꾸 틀리네요ㅠㅠ -
방금 풀었는데 한 번 돌려봐 주실 수 있나요? 파이썬 입니다
https://ideone.com/bxTdNh -
https://ideone.com/jOnUBS
그 테케커질때 이런방식이 문제가 생길지 여쭤본다고 말씀드렸는데 링크올립니다. -
2번 문제에서 C++ (next_permutation) 부분 질문이 있는데,
함수내에
pair<int,int> state[52][52]; // {arrival time, color}
를 선언을 했는데, RED , GREEN 값 이외에는 초기화가 안되어 있습니다.
그래서 문제가 있을것이라고 생각을 했는데 문제가 없더라구요
제 기억상 함수내에서 초기화를 안하면 쓰레기값이 들어갈것같은데
C++ 에서는 조금 다른지 궁금합니다.
-
C++도 초기화 없이 지역으로 배열을 선언하면 쓰레기 값이 들어가는것은 맞지만,
쓰레기값이 들어가 있는 부분은
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
범위 체크 부분에서 걸러지기 때문에
접근도 하지 않아 문제가 되지 않는게 아닐까요?
물론 친절한 킹갓독님이 보완해서 댓글 달아주실 꺼에요 ㅎㅎ -
int는 지역변수로 잡으면 쓰레기 값이 들어가지만 pair<int,int>는 {0,0}으로 초기화돼요
-
-
헉 모의고사 진행하신거도 몰랐어요ㅠㅠ 백준에 문제 언제 올라오나요? 갱적으로 풀고 해설강의 보겠습니다...ㅜㅜ
-
올라왔습니다
-
방금 풀어봤어요! 바쁘신데 좋은 구현문제 만들어주셔서 정말 감사합니다.
-
넵넵ㅎㅎ
-
-
감사합니다!!
-
넵!!!
-
-
풀이 코드에서 paste_check() 함수에서 if(!pastable)continue 이 부분이 이해가 되질 않습니다. ㅜㅜ
위조건에서 pastable = = false 인 경우를 전부 거른거 아닌가요?-
어느 코드의 어느 부분인가요??
-
질문이 첨이라 엉성하게 질문했네요...
스티커 붙이기 c++ 코드
paste_check()함수에서 if(!pastable)continue 이부분이 어떤 경우를 점검하는지 궁금합니다!
-
오잉 코드가 수정됐네요 ㅎㅎ 다시 분석해 보겠습니다!
-
노트북의 (x+i, y+j)에 스티커가 이미 부착되어있는데 지금 붙이려고 하는 스티커의 (i, j) 또한 1이어서 붙일 수 없으면 pastable = false가 되고, pastable이 false가 되면 더 이상 고려할 필요가 없으니 넘어가는 식이었던 것 같아요.
-
-
좋은 문제 감사합니다~!
-
(- -)(_ _)
-
-
Gaaaaaaaarden 문제에서 C++ 백트래킹 풀이 중에
do{
mx = max(mx, solve());
}while(next_permutation(brute, brute+candsz));
이 부분에 대해 궁금한 것이 있습니다.
brute 배열은 총 10개 까지 나올 수 있으므로 next_permutation을 돌리면 10!이 나오는게 아닌가요?
next_permutation 10!에다가 기본 bfs 50*50 하면 시간초과가 날 것 같은데 혹시 제가 잘못 알고 있나 여쭤봅니다!-
{1,1,2,2}로 next_permutation을 돌리면 4! = 24가지를 하는게 아니고
1122
1212
1221
2112
2121
2211
총 6가지만 돕니다. 그래서 저 코드의 상황에서도 10!이 아니라 (10 choose R) * (10-R choose G)개의 경우를 확인합니다. -
아하 그런거였군요 ! 감사합니다 ㅎㅎ
-
-
안녕하세요 바킹독님! 다름이 아니라 c++로 알고리즘 연습했는데 이번에 코테보는회사가 c++을 지원하지 않아 갑자기 자바로 연습해야하게 생겨서 질문 드립니다ㅠ 우선 외부 함수 선언 시 바킹독님 소스 보니까 static boolean pasteable(int x, int y) ~ 이런식으로 c++풀때랑 비슷하게 짜셨는데 프로그래머스 보니까 기본 틀이
class Solution {
public int solution(int bridge_length, int weight, int[] truck_weights) {
int answer = 0;
return answer;
}
}
이런식이더라구요ㅠㅠ 클래스로 하는거랑 함수로 하는거랑 컴파일 시 차이가 존재하는지 여쭤보겠습니다!
-
그냥 프로그래머스는 함수를 작성하는 방식으로 채점하고 BOJ는 표준 입출력으로 채점을 해서 그런건데 제가 질문을 제대로 이해한게 맞나요??
-
제가 자바를 잘 몰라서 질문을 제대로 못한거 같습니다ㅠㅠ 질문드리고 싶었던 것은 프로그래머스 format에서 c++은 그냥
int solution (vector<int> &arr){
return ans;
}
이런식인데, 왜 자바는
class solution{
public int solution (int [] arr){
}
}
왜 함수에 클래스로 싸져(?) 있는지 모르겠어요ㅠ -
저도 자바를 잘 아는건 아닌데 원래 자바의 각 .java 파일 하나하나가 클래스여서 그런거 아닐까요?
-
생각해보니 그런거 같네요. 다행히 다들 같은 조건이라 그런가 해당 코테는 합격했습니다! 2번 문제가 시뮬레이션이었는데 바킹독님께서 좋은 문제들을 많이 만들어주셔서 그걸로 훈련했더니 쉽게 풀었습니다. 자바 문법으로 바꾸는 과정 땜에 3번 문제를 못푼게 아쉬었지만요ㅠㅠ 감사합니다!!
-
도움이 됐다니 기쁘네요ㅎㅎ 앞으로도 좋은 일 많으시면 좋겠어요!!
-
-
-
BOJ가 워낙 익숙해서,,, ㅜㅜ 더블릿 화이팅..!!
-
-
안녕하세요 이 문제들의 Python 풀이에서 print() 대신 sys.stdout.write()를 쓴 이유가 궁금해서 질문 남겨봅니다!
-
print보다 sys.stdout.write가 더 빨라요
https://www.acmicpc.net/blog/view/57 -
해당 글은 예전에 이미 읽은 적이 있지만 print() 대신 sys.stdout.write()를 쓰는 경우는 https://www.acmicpc.net/problem/10989 이 문제에서 메모리 초과를 피하기 위해 사용한것 빼고는 본 적이 없는것 같아서 질문해 보았어요
여기 풀이하신 문제가 시간 제한이 아슬아슬해서 쓰신 건가요 아니면 실행 시간을 조금이라도 줄이기 위한 일종의 최적화라고 보면 될까요? -
마치 sync_with_stdio와 cin.tie를 매번 다는 것과 같다고 생각하면 될것같고, 입출력 양이 많지 않아서 그냥 input / print 써도 통과에 문제없을거에요
-
그렇군요 감사합니다
-